题目描述
Windy 有 N 个不同重量的球，从 1 个单位到 N 个单位。现在，他尝试以 1 到 N 的方式标记它们：
没有两个球共享相同的标签。
标签满足几个约束条件，例如“标有 a 的球比标有 b 的球轻”。
你能帮助windy找到解决办法吗？
输入
输入的第一行是测试用例的数量。每个测试用例的第一行包含两个整数，N (1 ≤ N ≤ 200) 和 M (0 ≤ M ≤ 40,000)。接下来的 M 行每行包含两个整数 a 和 b，表示标有 a 的球必须比标有 b 的球轻。 (1 ≤ a, b ≤ N) 每个测试用例前有一个空行。
输入样例:
5 4 0 4 1 1 1 4 2 1 2 2 1 4 1 2 1 4 1 3 2
输出样例
1 2 3 4 -1 -1 2 1 3 4 1 3 2 4
思路: 本题的意思是,给出N个标签球,标签球之间的大小关系已经给出,我们要做的是按照重量的大小给每一个标签球进行标号,重量大的标号也就大,如果某一次标号中多个球都满足标号的条件,那么按照球号大的进行先标号,标号也是1–N. 如果中间存在了环也就无法进行标号,那么解就不存在.
样例:
在样例中,先对3号求进行标号:label[3] = 5,然后删除3号球的两条边,这时1,2号都可进行标号,那么由于2号求号更大,所以先进行label[2] = 4,之后1,4号也可进行标号,同样先label[4] = 3,然后label[1] = 2,label[5] = 1; 在标号过程中,我们是按照出度为0的球进行标号.
由于题中没说明,则可能会出现重边,在构建时,如果边已经存在了,入度就不需要进行+1了.否则会出现,有的顶点其实没有入度边了,但入度数组中该大小还不为0.
解题思路:
建立原图的逆向图,这样在每次进行标号时,我们是依据入度为0进行搞的.由于中间可能出现多个球都可进行标号,所以我们不能再使用栈了,我们改用使用一个for(int i = n; i >= 1; i--) 在这个过程中我们先要寻找入度为0的球且是最大标号的那个,然后进行标号,从而进行下一轮.如果不能找到,则说明该图中存在环,结束即可. 对于每一次循环都会进行一次标号.
采用正向图,但处理的时候是根据出度为0的点进行标号的,同时该点的所有出度进行-1,之后的思路和上个思路相同.
参考代码
#include<iostream> #include<string.h> using namespace std; const int maxn = 210; int map[maxn][maxn],label[maxn],in[maxn],n,m,t,flag,T; void TopoSort(){ flag = 0; for(int i = n; i >= 1; i--){//采用循环来进行标号. //寻找入度为0的最大标号的球. t = 0;//用于存找到的入度为0的最大编号. for(int j = n; j>=1; j--){//从标号最大开始找,找到的第一个即是最大的那个. if(!in[j]){ t = j; break; } } if(!t){//如果没有找到则说明有环. flag = 1; break; } in[t] = -1;//入度改变,防止影响下一次入度为0节点的寻找. label[t] = i;//进行标号 for(int j = 1; j <= n; j++){//该点所有临界点的入度进行-1 if(map[t][j]){ in[j]--; } } } } int main() { int u,v; cin>>T; while(T--){ //初始化 memset(map,0,sizeof(map)); memset(label,0,sizeof(label)); memset(in,0,sizeof(in)); cin>>n>>m; for(int i = 1; i <= m; i++){ cin>>u>>v; if(!map[v][u]) {//如果已经读入过了就不再进行读入,防止重边影响Topo排序. map[v][u] = 1; in[u]++; } } TopoSort(); if(flag){//有环 cout<<"-1"<<endl; }else{ for(int i = 1; i <= n-1; i++){//标号成功则进行输出. cout<<label[i]<<" "; } cout<<label[n]<<endl; } } return 0; }
![洛谷P1216-[USACO1.5][IOI1994]数字三角形 Number Triangles（DP）](https://ucc.alicdn.com/images/user-upload-01/20200726134345890.png?x-oss-process=image/resize,h_160,m_lfit)