本文主要是介绍Poj 3687 Labeling Balls[拓扑排序]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：点击打开链接
很给力的道题，拓扑排序的应用，算是对TopSort认识更深了吧。
拓扑排序这里不做过多的解释，主要来说这道题的应用。
题目的意思就是给1——N质量的N个球贴标签，要求就是满足要求下的标签小的尽量轻。
没什么深入想，直接TopSort。果断WA，WA的。后来看题，发现了很多的问题。输出的是Label1-LabelN标签的重量。还有很多的问题没有看太清晰。
再看了几遍题意后，还是WA WA的。果断不知道怎么弄了。
拿来一组数据比较了一下，果断ANSWER是错误的。
后来我都有点混乱了。
我可以有两种操作：
一，我找到满足条件的质量最小的一次贴标签。
二，我还是找到满足条件的最小的标签给质量依次贴。
权衡操作复杂度来看，第一种比较简单。
上WA的代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;const int N=205;
bool vis[N];
int n,m,Enter[N];
vector<int> map[N];void TopSort(){int q[N],top=1;while(1){int cnt=0,p;for(int i=n;i>=1;i--)if(Enter[i]==0&&!vis[i]){cnt++;p=i;}if(cnt==0) break;else q[p]=top++;for(int i=0;i<map[p].size();i++)Enter[map[p][i]]--;vis[p]=true;}if(top-1==n){for(int i=1;i<=n;i++){for(int j=1;j<=top;j++)if(q[j]==i) printf("%d ",j);}}else printf("-1");printf("\n");
}
int main(){int T;scanf("%d",&T);while(T--){CLR(vis,0);CLR(Enter,0);CLR(map,0);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);map[a].push_back(b);Enter[b]++;}TopSort();}return 0;
}
比如这组数据
5 4
1 4
4 2
5 3
3 2
错误的程序错误输出为：
1 4 5 3 2
通过手模拟我们可以知道：
1 5 3 4 2
这是为什么呢？？？
因为，单入度为0的节点有多个的时候 ，我们选择的标准应该是什么？
有很多的朋友肯定会说当然是选择质量最小的啊。对，我也是这么想的。
但是，如果这样做的话，就会出现，后面出现更小的质量同样也满足条件。
比如 假设 1 3 5 4 2 和 1 5 3 4 2这两种， 条件同样满足。但是5先出现了入度为0 的情况。这样就不对了。
经过百度加上自己的理解，学会了普遍的反向建图的方法。
正确代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#define CLR(arr,val) memset(arr,val,sizeof(arr))
using namespace std;const int N=205;
bool vis[N];
int n,m,Enter[N];
bool map[N][N];void TopSort(){int q[N],top=n;while(top>0){int cnt=0,p;for(int i=1;i<=n;i++)if(Enter[i]==0&&!vis[i]){cnt++;p=i;}//面对多个入度为0的节点时，我们该怎么处理？//是 将小的节点进入序列 删边 再重新选点//还是 将所有的节点进入序列 删边 再选点？if(cnt==0) break;else q[top--]=p;for(int i=1;i<=n;i++)if(map[p][i]) Enter[i]--;vis[p]=true;}if(top==0){//这里明显是找到合适的标签贴到ball上.for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)if(q[j]==i) printf("%d%c",j,i==n?'\n':' ');}}else printf("-1\n");
}
int main(){int T;scanf("%d",&T);while(T--){CLR(vis,0);CLR(Enter,0);CLR(map,0);scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int a,b;scanf("%d%d",&a,&b);if(!map[b][a]){map[b][a]=true;Enter[a]++;}}TopSort();}return 0;
}
反向建图，找最大的标签给最大质量的ball贴。
这里吧第一种操作和第二种操作搞晕了。
如果你是第一种操作那么相当于把标签的顺序已经排好（1-n），需要挑选合适质量的球。
第二种，反之。
好题。！
这篇关于Poj 3687 Labeling Balls[拓扑排序]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
