分析

• 这一题是一道差分约束的题目，但是是一个简化版的差分约束，可以使用差分约束求解，但是有种”大炮打蚊子”的感觉，这一题没必要使用差分约束求解。

• 此题让我们求最小值，我们应该使用最长路（不懂的话可以参考这里），题目的不等式条件是：

① $a \ge b + 1$，相当于建一条从b指向a的边权为1的边；

② $a \ge 100$，建立虚拟源点$x_0 = 0$，则$a \ge x_0 + 100$，建立一条从$x_0$到a边权为100的边。其实代码中不需要真实建立出来

• 关于差分约束的三道题目的对比：

（1）AcWing 1169. 糖果：关于这一题的讲解网址；这一题的边权是0或者1，其实是负数也可以，差分约束可以求解任意边权的问题。

（2）AcWing 368. 银河：关于这一题的讲解网址；抽象之后，这一题和AcWing 1169. 糖果是一模一样的，边权是0或者1，只要边权都是非负的，然后让我们求最长路，我们就可以使用有向图的强联通分量求解（如果边权都是非正的，然后让我们求最短路，我们也可以使用有向图的SCC求解）。

（3）AcWing 1192. 奖金：也就是本题，因为所有的边权都是相同的（为1），直接使用拓扑排序求解即可，若拓扑排序无解，说明图中一定含有正环，无解；否则有解的话说明是拓扑图，我们可以直接递推求解最长路径。

• 值得一提的是我们并不需要建立虚拟源点$x_0$，因为有解的话图一定是DAG，可以将所有点的初始距离初始化为100,，然后递推求解即可。

#include <iostream>
#include <cstring>

using namespace std;

const int N = 10010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;  // 权重只可能为1，因此不用存储
int q[N];  // 普通队列
int d[N];  // 入度
int dist[N];  // 距离

void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

bool topsort() {

    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
        if (!d[i]) 
            q[++tt] = i;

    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; ~i; i = ne[i]) {
            int j = e[i];
            if (--d[j] == 0)
                q[++tt] = j;
        }
    }

    return tt == n - 1;
}

int main() {

    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(b, a);
        d[a]++;
    }

    if (!topsort()) puts("Poor Xed");
    else {
        // 递推求最长路径
        for (int i = 1; i <= n; i++) dist[i] = 100;

        for (int i = 0; i < n; i++) {
            int j = q[i];
            for (int k = h[j]; ~k; k = ne[k])
                dist[e[k]] = max(dist[e[k]], dist[j] + 1);
        }

        int res = 0;
        for (int i = 1; i <= n; i++) res += dist[i];

        printf("%d\n", res);
    }

    return 0;
}