大体思路就是简单的拓扑排序。
写的时候没有看模板，都是自己一点一点改的，应该没有模板效率高。
还用了一点优先队列的思想，用了并查集的方法检查是否存在环。
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 5 using namespace std; 6 7 struct N 8 { 9 int data; 10 int n,money; 11 N *next; 12 }*head[10010]; 13 14 void init(int n)//初始化函数 15 { 16 for(int i = 1;i <= n; i++) 17 { 18 head[i] = (struct N *)malloc(sizeof(struct N)); 19 head[i]->n = 0; 20 head[i]->data = -1; 21 head[i]->next = NULL; 22 head[i]->money = -1; 23 } 24 } 25 26 int h[10010];//为并查集准备的数组 27 28 int seek(int u,int v)//并查集 29 { 30 while(h[v] != v) 31 { 32 v = h[v]; 33 } 34 if(u != v) {h[u] = v;return 1;} 35 else return 0; 36 } 37 38 void link(int u,int v) 39 { 40 N *p1 = head[u],*p2 = head[u]->next; 41 for(;p2 != NULL; p1 = p1->next,p2 = p2->next) 42 { 43 if(p2->data == v) return; 44 if(p1->data < v && v < p2->data) 45 { 46 N *p = (struct N *)malloc(sizeof(struct N)); 47 p->data = v; 48 head[v]->n++; 49 p->next = p1->next; 50 p1->next = p; 51 return; 52 } 53 } 54 N *p = (struct N *)malloc(sizeof(struct N)); 55 p->data = v; 56 head[v]->n++; 57 p->next = NULL; 58 p1->next = p; 59 return; 60 } 61 62 int sum; 63 64 void check(int u,int min) 65 { 66 int q[10001],s = 0,e = 0; 67 for(N *p = head[u]->next; p != NULL; p = p->next) 68 { 69 if(head[p->data]->money == -1)//如果此点第一次被访问，直接将min加入sum 70 { 71 sum += min; 72 head[p->data]->money = min; 73 } 74 else if(head[p->data]->money < min)//如果此点已经被访问，则需比较当前的min是否大于其当前的奖励。 75 { 76 sum = sum + (min - head[p->data]->money); 77 head[p->data]->money = min; 78 } 79 q[e++] = p->data; 80 } 81 for(s = 0,min = min+1;s < e; s++) 82 { 83 check(q[s],min); 84 } 85 } 86 87 int main() 88 { 89 90 int m,n,u,v,i,flag; 91 while(scanf("%d %d",&n,&m) != EOF) 92 { 93 for(i = 1;i <= n; i++) 94 h[i] = i; 95 init(n); 96 flag = 1; 97 while(m--) 98 { 99 scanf("%d %d",&v,&u); 100 if(flag && seek(u,v))//seek——并查集 用来检查是否存在环 101 { 102 link(u,v); 103 } 104 else flag = 0; 105 } 106 if(flag) 107 { 108 sum = 888*n; 109 for(i = 1;i <= n; i++) 110 { 111 if(head[i]->n == 0) 112 check(i,1); 113 } 114 printf("%d\n",sum); 115 } 116 else printf("-1\n"); 117 } 118 return 0; 119 }
转载于:https://www.cnblogs.com/zmx354/archive/2013/04/19/3031431.html
相关资源：JAVA上百实例源码以及开源项目