Description
有$n$道菜,编号越小的越美味(最美味的是$1$号菜品)。现在给出一些形如$(i,j)$的限制,表示$i$号菜品必须在$j$号菜品之前制作。要求出一个最优的菜肴的制作顺序,使得Karry5307能尽量先吃到美味的菜肴。无解输出Impossible!
Sol
如果你是贪心地求字典序小的,Karry5307不一定能吃到尽量先地吃到最美味的菜品。
比如说共4 道菜肴,两条限制$(3,1)$、$(4,1)$,那么制作顺序是 $3,4,1,2$。但是你贪心就会变成$2,3,4,1$但是如果反过来处理,建一个反图,求一个反向字典序最大的拓扑序。那么就会有大的数尽量靠前的情况出现,于是交小的数尽量靠后,于是反过来就是小的数尽量靠前了。
Code
果然代码环节还是我最喜欢的
#include <bits/stdc++.h>
using namespace std;
const int SIZE = 1e5 + 5;
int q, n, m, num;
int head[SIZE], deg[SIZE];
struct node {
int to, nxt;
} edge[SIZE];
namespace ae86 {
const int bufl = 1 << 15;
char buf[bufl], *s = buf, *t = buf;
inline int fetch() {
if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
return *s++;
}
inline int read() {
int a = 0, b = 1, c = fetch();
while (!isdigit(c))b ^= c == '-', c = fetch();
while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
return b ? a : -a;
}
}
using ae86::read;
inline void addEdge(int u, int v)
{
edge[++ num].to = v, edge[num].nxt = head[u];
head[u] = num;
}
inline void top()
{
std::priority_queue < int > q;
std::vector < int > ans;
for (int i = 1; i <= n; ++ i) {
if (!deg[i]) q.push(i);
}
while (!q.empty()) {
int u = q.top(), v;
ans.push_back(u);
q.pop();
for (int i = head[u]; i; i = edge[i].nxt) {
v = edge[i].to;
-- deg[v];
if (!deg[v]) q.push(v);
}
}
if ((int) ans.size() != n) puts("Impossible!");
else {
for (auto i = ans.end() - 1; i != ans.begin() - 1; -- i) printf("%d ", *i);
putchar('\n');
}
}
int main()
{
// freopen("code.in", "r", stdin);
// freopen("code.out", "w", stdout);
q = read();
while (q --) {
n = read(), m = read();
for (int i = 1, u, v; i <= m; ++ i) {
u = read(), v = read();
addEdge(v, u); ++ deg[u];
}
top();
num = 0;
memset(head, 0, sizeof(head));
memset(deg, 0, sizeof(deg));
}
return 0;
}