【拓扑排序】HDU 2647 Reward【2012/3/25更新】

基德KID.1412

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[20005];int ind[M], p[M], cnt, money[M], 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[cnt].v = v, e[cnt].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[e.v] == 0)                {                    money[e.v] = money + 1;                    q.push (e.v);                }            }        }        if (num < n) ans = -1;        printf ("%d\n", ans);    }    return 0;}