POJ 3687 Labeling Balls

　　题意：有N个球给出一些轻重关系排除拓扑序列若拓扑排序不唯一则尽量让序号小的轻。输出为该球在拓扑排序中的位置。

　　解题思路：让入度为零的点进栈，若存在多个入度为零的点，则选取编号最大的。

　　不会的时候难了一13，会了就感觉水了一13。。。。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cmath>
  5 #include <cstdlib>
  6 #include <algorithm>
  7 #include <queue>
  8 
  9 using namespace std;
 10 
 11 int head[210],edge[210][40010];
 12 
 13 struct P
 14 {
 15     int i,o,mark;
 16 };
 17 
 18 void link(int u,int v)
 19 {
 20     edge[u][head[u]++] = v;
 21 }
 22 
 23 int s[210];
 24 int top;
 25 
 26 void toposort(int in,int n,P *org)
 27 {
 28     P *point = (P *)malloc((n+2)*sizeof(P));
 29     int i,t;
 30 
 31     for(i = 0 ;i <= n; i++)
 32         point[i] = org[i];
 33 
 34     queue<int> q;
 35     q.push(in);
 36     s[top++] = in;
 37     point[in].mark = 0;
 38 
 39     while(!q.empty())
 40     {
 41         t = q.front();
 42         q.pop();
 43 
 44         for(i = 0;i < head[t]; i++)
 45         {
 46             point[edge[t][i]].i--;
 47         }
 48 
 49         for(i = n;i >= 1; i--)
 50         {
 51             if(point[i].mark == 1 && point[i].i == 0)
 52             {
 53                 q.push(i);
 54                 s[top++] = i;
 55 
 56                 point[i].mark = 0;
 57                 break;
 58             }
 59         }
 60     }
 61 }
 62 
 63 int heavy[210];
 64 
 65 int main()
 66 {
 67     int T;
 68     int n,m;
 69     int u,v;
 70 
 71     int i;
 72 
 73     cin>>T;
 74     while(T--)
 75     {
 76         P point[210];
 77 
 78         cin>>n>>m;
 79 
 80         for(i = 0; i <= n; i++)
 81         {
 82             head[i] = 0;
 83             point[i].i = point[i].o = 0;
 84             point[i].mark = 1;
 85         }
 86 
 87         for(i = 0; i < m; i++)
 88         {
 89             cin>>v>>u;
 90             link(u,v);
 91             point[u].mark = point[v].mark = 1;
 92             point[u].o++;
 93             point[v].i++;
 94         }
 95         top = 0;
 96         for(i = n; i >= 1; i--)
 97         {
 98             if(point[i].i == 0)
 99             {
100                 toposort(i,n,point);
101                 break;
102             }
103         }
104 
105         if(top == n)
106         {
107             for(top--; top >= 0; top--)
108             {
109                 heavy[s[top]] = n-top;
110             }
111 
112             printf("%d",heavy[1]);
113 
114             for(i = 2; i <= n; i++)
115                 printf(" %d",heavy[i]);
116             printf("
");
117         }
118         else printf("-1
");
119     }
120     return 0;
121 }

View Code