poj 3687 Labeling Balls
Description
Windy has N balls of distinct weights from 1 unit to N units. Now he tries to label them with 1 to N in such a way that:
- No two balls share the same label.
- The labeling satisfies several constrains like "The ball labeled with a is lighter than the one labeled with b".
Can you help windy to find a solution?
Input
The first line of input is the number of test case. The first line of each test case contains two integers, N (1 ≤ N ≤ 200) and M (0 ≤ M ≤ 40,000). The next M line each contain two integers a and b indicating the ball labeled with a must be lighter than the one labeled with b. (1 ≤ a, b ≤ N) There is a blank line before each test case.
Output
For each test case output on a single line the balls' weights from label 1 to label N. If several solutions exist, you should output the one with the smallest weight for label 1, then with the smallest weight for label 2, then with the smallest weight for label 3 and so on... If no solution exists, output -1 instead.
Sample Input
5 4 0 4 1 1 1 4 2 1 2 2 1 4 1 2 1 4 1 3 2
Sample Output
1 2 3 4 -1 -1 2 1 3 4 1 3 2 4
题意：：N个标签分别是1,2,3......N。N个小球，质量分别是1,2,3.....N。现在给球贴标签，有M个限制条件。其中每个限制条件为贴标签a的球要比贴标签b的球轻。
依次输出标签1的球的质量，标签2的球的质量.........且字典序最小。
题解：如果没有字典序最小的限制条件，那么标签a比标签b轻，则建一条边从a到b。如果图存在环在，则无解。如果图没环，直接进行拓扑排序（正向），将每次选出的点贴给当前最小的质量的
球，
即可求得一组解。
题目要求让字典序最小，刚开始想的是正向建图，然后每次选取一个最小的质量用队列进行拓扑排序，可是这样是错误的，这样只能保证在每一步（当前情况，题目要求得是结果）的选择中使当前入度为0并且编号最小的球重量最小，
并不能保证得到的结果中编号最小的球重量最轻。后来采用了反向建图，在拓扑排序中每一步选择当前最大的编号给他分配当前最大的重量（即此时入度为零的球），这样可以保证得到的结果f
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #include <cstdlib> 6 #include <cmath> 7 #include <queue> 8 #include <stack> 9 #include <limits> 10 #define MAX 205 11 12 using namespace std; 13 int G[MAX][MAX]; 14 int in[MAX]; 15 int data[MAX]; 16 int main() 17 { 18 int t; 19 scanf("%d",&t); 20 while(t--) 21 { 22 // getchar(); 23 int a,b,m,n; 24 scanf("%d%d",&n,&m); 25 memset(G,0,sizeof(G)); 26 memset(in,0,sizeof(in)); 27 while(m--) 28 { 29 scanf("%d%d",&a,&b); 30 if(!G[b][a])//重复边 31 { 32 G[b][a]=1; 33 in[a]++; 34 } 35 } 36 int k=0; 37 for(int i=n; i>=1; i--) 38 { 39 int flag=1,s; 40 for(int j=n; j>=1; j--) 41 if(in[j]==0) 42 { 43 data[j]=i;//i为最外层的循环，将当前度为零的即最大的质量放在最大编号球 44 in[j]--; 45 flag=0; 46 k++; 47 s=j; 48 break; 49 } 50 if(flag) 51 { 52 k=0; 53 break; 54 } 55 for(int j=n; j>=1; j--) 56 if(G[s][j]) 57 in[j]--; 58 } 59 if(k!=n) 60 { 61 printf("-1"); printf("\n"); 62 } 63 else 64 for(int i=1;i<=n;i++) 65 printf("%d%c",data[i],i==n?'\n':' '); 66 67 } 68 return 0; 69 }
