【拓扑排序】HDU 2647 Reward【2012/3/25更新】
http://acm.hdu.edu.cn/showproblem.php?pid=2647题意：先给出人数n和关系数m，再给出工人之间的工资大小关系，例如给出a b表示a>b，求老板至少要给多少工资【注：工人至少有888元的工资】
Sample Input
2 1
1 2
2 2
1 2
2 1
6 5
2 4
3 6
3 5
1 2
1 3
4 3
1 2
3 4
2 3
Sample Output
1777
-1
5532
3558
#include <iostream>#include <queue>using namespace std;#define M 10005struct edge{ int v, w, nxt;}e;int ind, p, cnt, money, n;void init (){ cnt = 0; memset (p, -1, sizeof(p)); memset (ind, 0, sizeof(ind)); for (int i = 1; i <= n; i++) money = 888;}void addedge (int u, int v){ e.v = v, e.nxt = p, p = cnt++;}int main(){ int m, u, v, i, num, ans = 0; while (~scanf ("%d%d", &n, &m)) { init (); while (m--) { scanf ("%d%d", &u, &v); addedge (v, u);//逆向思维 ind++; } queue<int> q; for (i = 1; i <= n; i++) if (ind == 0) q.push (i); num = ans = 0; while (!q.empty()) { u = q.front(); q.pop(); ans += money;//累加确定工资 num++; for (i = p; i != -1; i = e.nxt) { if (--ind.v] == 0) { money.v] = money + 1; q.push (e.v); } } } if (num < n) ans = -1; printf ("%d\n", ans); } return 0;}
页:
[1]