HDU 2647（拓扑排序）

拓扑排序

题意：输入n行数据a，b ，表示a的钱数大于b的钱数，最低的人分的的钱数为888，问最少需要多少钱可以分给员工

思路：标准的拓扑排序，不过这题需要逆向拓扑

注意点：1、如何判断途中有换，或者说有的点没有选择到，用个int整型cnt，利用拓扑排序的特点，每个点只查找一次，所以当cnt==n的时候，输出sum。

2、多组输入不要忘了初始化数组之类的

 1 #include <iostream>
 2 #include <cmath>
 3 #include <cstdio>
 4 #include <cstring>
 5 #include <string>
 6 #include <map>
 7 #include <iomanip>
 8 #include <algorithm>
 9 #include <queue>
10 #include <stack>
11 #include <set>
12 #include <vector>
13 //const int maxn = 1e5+5;
14 #define ll long long
15 #define MAX INT_MAX
16 #define FOR(i,a,b) for( ll i = a;i <= b;++i)
17 using namespace std;
18 int n,m,sum,head,headmoney,a,b,cnt;
19 int degree[11000];　　　　　　//度，我就不多说了 
20 vector<int>vec[11000];　　　　//存此节点下的子节点
21 queue<int>que;　　　　　　　　　　//存接下来思考的节点
22 int main()
23 {
24     //    freopen("D:\common_text\code_stream\in.txt","r",stdin);
25     //    freopen("D:\common_text\code_stream\out.txt","w",stdout);
26     while(scanf("%d%d",&n,&m)!=EOF)
27     {
28         memset(degree,0,sizeof(degree));
29         while(!que.empty()) que.pop();
30         memset(vec,0,sizeof(vec));
31         sum=0;
32         cnt=0;
33 
34 
35         while(m--)
36         {
37             cin>>a>>b;
38             if(a!=b)
39             {
40                 vec[b].push_back(a);
41                 degree[a]++;
42             }
43 
44         }
45 
46         for(int i=1;i<=n;++i)
47         {
48             if(degree[i]==0)
49             {
50                 //cnt++;
51                 //sum+=888;
52                 que.push(i);
53                 que.push(888);
54             }
55         }
56         while(!que.empty())
57         {
58             cnt++;
59 
60             head=que.front();
61             que.pop();
62             headmoney=que.front();
63             que.pop();
64             sum+=headmoney;
65             for(int i=0;i<vec[head].size();++i)
66             {
67                 if(--degree[vec[head][i]]==0)
68                 {
69                     que.push(vec[head][i]);
70                     que.push(headmoney+1);
71                 }
72             }
73         }
74         if(cnt==n)
75         {
76             cout<<sum<<endl;
77         }
78         else cout<<"-1"<<endl;
79 
80 
81 
82         }
83 
84 }