HDU 2647 Reward

大体思路就是简单的拓扑排序。
写的时候没有看模板，都是自己一点一点改的，应该没有模板效率高。
还用了一点优先队列的思想，用了并查集的方法检查是否存在环。
  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 }