HDU - 2647 - Reward(拓扑排序、判环)

题目链接
题目大意：你有n个人和m对关系，每对关系规定给前者的钱必须比后者多。问你给n个人的最少工资是多少。
??这题如果正向建图的话不太好做，因为我们要知道第一个人应该给多少好就得求从第一个点到最后一个点的距离，但是如果我们反向建图的话，就很好做了。我们反向建图，每条边连着的下一个点给的
钱比当前的点多1就好。注意可能有些点的关系是平行的。

const int maxn = 1e4+10;
vector<int> e[maxn];
int n, m, in[maxn]; ll ans = 0;
bool topo() {
    queue<P> qe;
    for (int i = 1; i<=n; ++i)
        if (!in[i]) qe.push(P(i, 888));
    ans = 0; int cnt = 0;
    while(!qe.empty()) {
        ++cnt;
        P t = qe.front(); qe.pop();
        int u = t.first, w = t.second;
        ans += (ll)w; 
        for (auto v : e[u])
            if (--in[v] == 0) qe.push(P(v, w+1));
    }
    return cnt != n;
}
int main(void) {
    while(~scanf("%d%d", &n, &m)) {
        for (int i = 0, a, b; i<m; ++i) {
            scanf("%d%d", &a, &b);
            e[b].push_back(a);
            ++in[a];
        }
        if (topo()) printf("-1\n");
        else printf("%lld\n", ans);
        zero(in);
        for (int i = 0; i<=n; ++i) e[i].clear();
    }
    return 0;
}

HDU - 2647 - Reward(拓扑排序、判环)

原文：https://www.cnblogs.com/shuitiangong/p/12634388.html