毒瘤题。。。。
题意：每个球都有一个重量，然后有n组约束条件，每次 A B ，代表着A标号的球 < B标号的球。最后让你输出每个标号的重量，如果有多个解决方案，那么尽量使得编号小的重量小。也就是说排列的字典序最小。如果不存在可能的排列输出-1。
思路：一开始当成模板题来做的我付出了惨痛的代价。。。
一看题目，可以建图进行拓扑排序，但不知道为什么一直Wa，后来看了别人的题解发现自己想的太简单了。。。
首先，正向拓扑排序 优先队列每次选取最小编号的做法，是错的。
拿 这位大佬 的图来说事。
优先选取 最小编号的序列为 14532 ，重量结果为 15423
可是 你如果选的是 15342 重量结果为 15342 明显字典序比上面小
所以我们正向拓扑贪心的思路是错的。可以明显，让标号越小的越往前 越好。正向拓扑贪心不满足，可是反向建图拓扑排序呢？
按上图，反向建图，每次尽可能选最大，首先选2，然后4 3 5 1 ，这个倒序显然是 15342，所以反向建图拓扑满足我们想要的。
AC Code：
#include<iostream> #include<cstring> #include<queue> #include<map> #include<set> #include<stack> #include<cmath> #include<cstdio> #include<iomanip> #include<sstream> #include<algorithm> using namespace std; #define read(x) scanf("%d",&x) #define Read(x,y) scanf("%d%d",&x,&y) #define sRead(x,y,z) scanf("%d%d%d",&x,&y,&z) #define gc(x) scanf(" %c",&x); #define mmt(x,y) memset(x,y,sizeof x) #define write(x) prllf("%d\n",x) #define INF 0x3f3f3f3f #define ll long long #define mod 998244353 #define pdd pair<double,double> const int N= 1e5+5; int head[205],tot; struct Edge { int next; int to; }edge[2*40000+5]; int deg[205]; int a[205];int cnt = 0; inline void add(int from,int to) { edge[++tot].next = head[from]; edge[tot].to = to; head[from] = tot; deg[to] ++; } inline void init() { mmt(deg,0); mmt(head,-1); tot = 0; } bool topsort(int n){ cnt = 0; priority_queue<int> Q;//每次选最大 for(int i = 1;i <= n;++i) if(deg[i] == 0) Q.push(i); while(Q.size()){ int x = Q.top(); Q.pop(); a[++cnt] = x; for(int i = head[x];~i;i = edge[i].next){ int y = edge[i].to; if(-- deg[y] == 0) Q.push(y); } } if(cnt < n) return 0; else return 1; } int w[205]; int main() { #ifndef ONLINE_JUDGE freopen("input.txt","r",stdin); #endif // ONLINE_JUDGE int T; int n,m; read(T); while(T--){ init(); scanf("%d%d",&n,&m); int u,v; for(int i = 1;i <= m;++i){ Read(u,v); add(v,u);//建反图 } if(topsort(n)) { int wo = n; for(int i = 1;i <= n;++i){ w[a[i]] = wo--; } for(int i = 1;i <= n;++i) cout<<w[i]<<" "; puts(""); } else cout<<-1<<endl; } }
