Poj 3687 Labeling Balls (拓扑排序) 今天药忘吃喽~ 2022-08-25 09:13 2阅读 0赞 题意：n个重量为1~n的球，给定一些编号间的重量比较关系，现在给每个球编号，在符合条件的前提下使得编号小的球重量小。（先保证1号球最轻，其次2号……） 思路：拓扑排序，反向建图。利用优先队列保证每次被处理点的编号最小。 #include <cstdio> #include <cstring> #include <queue> using namespace std; const int N=205; struct Node { int id,degree; //初始编号 入度 bool operator < (const Node &a) const { return id<a.id; } }data[N]; int n,m,cnt; bool graph[N][N],vis[N]; int ans[N],s[N]; bool Deal () { priority_queue <Node> q; int i; for (i=1;i<=n;i++) //所有入度为0的点先入队 if (data[i].degree==0) q.push(data[i]); while (!q.empty()) { Node cur=q.top(); q.pop(); if (cur.degree==0 && vis[cur.id]==false) { s[cnt++]=cur.id; //记录处理顺序 vis[cur.id]=true; for (i=1;i<=n;i++) if (vis[ data[i].id ]==false) { if (graph[cur.id][data[i].id]) data[i].degree--; if (data[i].degree==0) q.push(data[i]); } } } if (cnt<=n) return true; //有环 return false; } int main () { int T,i; scanf("%d",&T); while (T--) { scanf("%d%d",&n,&m); for (i=1;i<=n;i++) data[i].id=i,data[i].degree=0; cnt=1; memset(graph,false,sizeof(graph)); memset(vis,false,sizeof(vis)); memset(ans,0,sizeof(ans)); memset(s,0,sizeof(s)); while (m--) { int a,b; scanf("%d%d",&a,&b); if (graph[b][a]==false) {//处理重边,避免影响入度 graph[b][a]=true; data[a].degree++; } } if (Deal()) printf("-1\n"); else { for (i=1;i<cnt;i++) ans[ s[cnt-i] ] = i; for (i=1;i<=n;i++) printf(i==n?"%d\n":"%d ",ans[i]); } } return 0; } /* 测试数据转自 http://poj.org/showmessage?message_id=145313 2 5 4 5 1 4 2 1 3 2 3 10 5 4 1 8 1 7 8 4 1 2 8 ans: 2 4 5 3 1 逆向建图 5 1 6 2 7 8 3 4 9 10 没有判重边的话就输出 -1 */
还没有评论，来说两句吧...