HDU 2647 拓扑排序

题意：每个人的工资至少888，然后有m个条件，前者比后者要多。求最少工资。

分析：

最开始的开邻接矩阵的肯定超时，如果dfs，会出现由于刚开始不是从入度为0的点出发，后期修改不了。比较麻烦。

正确方式是，用队列实现，不需要像普通队列一样，用vis数组标记，而是根据入度是否为0的标准加入队列。

  1 /*
  2 #include <bits/stdc++.h>
  3 
  4 using namespace std;
  5 
  6 const int maxn = 10000+5;
  7 int n,m;
  8 
  9 vector<int> G[maxn];
 10 
 11 int c[maxn];
 12 int d[maxn];
 13 bool dfs(int u,int k) {
 14     c[u] = -1;
 15     //d[u] = k;
 16     for(int i=0;i<G[u].size();i++) {
 17         int v = G[u][i];
 18 
 19         if(c[v]<0) return false;
 20         else if(!c[v]&&!dfs(v,k+1)) return false;
 21 
 22     }
 23 
 24     c[u] = 1;
 25     return true;
 26 
 27 }
 28 
 29 bool toposort() {
 30     memset(c,0,sizeof(c));
 31     for(int u=1;u<=n;u++) {
 32         if(!c[u])
 33             if(!dfs(u,0))
 34                 return false;
 35     }
 36     return true;
 37 }
 38 
 39 int main()
 40 {
 41     freopen("in.txt","r",stdin);
 42     while(scanf("%d%d",&n,&m)!=EOF) {
 43 
 44         for(int i=0;i<=n;i++)
 45             G[i].clear();
 46 
 47         for(int i=0;i<m;i++) {
 48             int u,v;
 49             scanf("%d%d",&u,&v);
 50             G[v].push_back(u);
 51         }
 52 
 53         memset(d,0,sizeof(d));
 54 
 55         int sum = 0;
 56 
 57 
 58         if(toposort()) {
 59             for(int i=1;i<=n;i++) {
 60                 sum+=d[i];
 61             }
 62             printf("%d
",888*n+sum);
 63         }
 64         else puts("-1");
 65 
 66 
 67     }
 68     return 0;
 69 }
 70 */
 71 
 72 
 73 #include <bits/stdc++.h>
 74 
 75 using namespace std;
 76 
 77 const int maxn = 10000+10;
 78 
 79 vector<int> G[maxn];
 80 int degree[maxn];
 81 
 82 
 83 int main()
 84 {
 85     //freopen("in.txt","r",stdin);
 86     int n,m;
 87     while(scanf("%d%d",&n,&m)!=EOF) {
 88 
 89         for(int i=1;i<=n;i++) {
 90             G[i].clear();
 91         }
 92         memset(degree,0,sizeof(degree));
 93 
 94         for(int i=0;i<m;i++) {
 95             int u,v;
 96             scanf("%d%d",&u,&v);
 97             G[v].push_back(u);
 98             degree[u]++;
 99         }
100 
101         queue<pair<int,int> > Q;
102 
103         int cnt = 0,ans = 0;
104         for(int i=1;i<=n;i++) {
105             if(!degree[i]) {
106                 Q.push(make_pair(i,888));
107                 ans+=888;
108                 cnt++;
109             }
110         }
111 
112         while(!Q.empty()) {
113             pair<int,int> u = Q.front();
114             Q.pop();
115 
116             for(int i=0;i<G[u.first].size();i++) {
117                 int v = G[u.first][i];
118                 degree[v]--;
119                 if(!degree[v]) {
120                     Q.push(make_pair(v,u.second+1));
121                     ans += u.second + 1;
122                     cnt++;
123                 }
124             }
125 
126         }
127 
128         if(cnt==n)
129             printf("%d
",ans);
130         else puts("-1");
131 
132 
133 
134     }
135     return 0;
136 }

View Code