这道题数据比较大，得用领阶表，表示压力很大。。。。
这道题有两个地方值得注意。
第一个地方就是怎么确定是否有环，确定的办法就是就是根据离散数学（离散86，烧包加雄起~）的入度来说，当遍历一边并且更新后查找入度为零的点应该有N个（一共N个点）。用一个计数器num去计算是否为n。
第二个地方就是方向思维。按理说我们应该用大的作小的父亲，但是当我们建立完一个拓扑表以后，我们如果按照以大的作为父亲的话，我们在计算最顶端的权值（暂且叫为权值吧），即最高点的薪水时，用起点与后续节点相比较加一时不准的，因为后面节点的值会随着向后遍历而改变，而对于遍历完的值无法改变。所以我们不如去找最为固定的点，即最小薪水的点，来一次往上去寻找，也就是用了DP中从下而上的逆向思想，来计算总薪水。
但是有人会担心，即使如此也可能使得已被遍历过的值不在改变，从而不能保证结果的准确性。比如这个数据：
4 4（4个数，4个关系）
2 1
3 1
3 2
1 4
从1开始遍历的话，到了2，3组数据可以没问题，但是最后一组呢？？？请记住，我们是按拓扑排序的最低点出发，即4，入度为零的点开始搜索遍历。这样就没有问题了。
以下是代码
View Code
1 #include <stdio.h> 2 #include <string.h> 3 struct node 4 { 5 int u,v; 6 int next; 7 }g[20005];//边 8 struct degree 9 { 10 int i,w; 11 } head[10005];//头结点，也就是有多少个点。 12 int t,count; 13 int in[10005];//记录入度。 14 void init(int n) 15 { 16 int i; 17 for(i = 0;i <= n;i++) 18 head[i].i = -1,head[i].w = 888,in[i] = 0; 19 t = 0; 20 } 21 void add(int u,int v)//加入边，建立关系。分清谁是该节点的代表值，谁是子节点。 22 { 23 in[u]++;//子节点的入度+1； 24 g[t].u = u; 25 g[t].v = v; 26 g[t].next = head[v].i; 27 head[v].i = t;//v才是父亲 28 t++; 29 } 30 31 int main() 32 { 33 int n,m,i,j,u,v,num,p; 34 while(~scanf("%d %d",&n,&m)) 35 { 36 init(n); 37 for(i = 0;i < m;i++) 38 { 39 scanf("%d %d",&u,&v); 40 add(u,v);//v才是父亲 41 } 42 num = n;//给计数器赋值 43 for(i = 0;i < n;i++) 44 { 45 for(j = 1;j <= n;j++) 46 { 47 if(in[j] == 0) 48 { 49 num--;//出现符合节点，计数器减一。 50 in[j] = -1; 51 break; 52 } 53 } 54 if(j > n) 55 break; 56 p = head[j].i; 57 while(p != -1) 58 { 59 in[g[p].u]--; 60 if(head[g[p].u].w <= head[j].w) 61 head[g[p].u].w = head[j].w+1; 62 p = g[p].next; 63 } 64 } 65 int sum; 66 sum = 0; 67 if(num)//说明出现了环。 68 puts("-1"); 69 else { 70 for(i = 1;i <= n;i++) sum+=head[i].w; 71 printf("%d\n",sum); 72 } 73 } 74 }