poj3687Labeling Balls

样例太唬人了，求得是从1到N重量而不是排好序的标签

逆向建图把最重的赋给第一个入度为0的标签如有多个赋给标签大的这样能保证重量大的在后面

View Code

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int to[301],w[301][301],de[301],tt[301];
 7 int topo(int n)
 8 {
 9     int i,j,k,g,f;
10     for(i = n; i >= 1 ; i--)
11     {
12         f = 1;
13         for(j = n; j >= 1 ; j--)
14         {
15             if(de[j]==0)
16             {
17                 f = 0 ;
18                 de[j]--;
19                 k = j;
20                 to[k] = i;
21                 for(g = 1; g <= n; g++)
22                 if(w[k][g])
23                 de[g]--;
24                 break;
25             }
26         }
27         if(f)
28         break;
29     }
30     return f;
31 }
32 int main()
33 {
34     int t,n,m,i,j,k,a,b;
35     cin>>t;
36     while(t--)
37     {
38         int flag = 1;
39         memset(de,0,sizeof(de));
40         memset(w,0,sizeof(w));
41         cin>>n>>m;
42         for(i = 1; i <=  m ; i++)
43         {
44             cin>>a>>b;
45             if(!w[b][a])
46             {
47                 w[b][a] = 1;
48                 de[a]++;
49             }
50             if(a==b)
51             flag = 0;
52         }
53         if(!flag)
54         {
55             puts("-1");
56             continue;
57         }
58         if(topo(n))
59         {
60             puts("-1");
61             continue;
62         }
63         else
64         {
65             for(i = 1;i < n ; i++)
66             cout<<to[i]<<" ";
67             cout<<to[n]<<endl;
68         }
69     }
70     return 0;
71 }