1192. 奖金

由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。

公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。

于是Mr.Z下令召开 m 方会谈。

每位参加会谈的代表提出了自己的意见：“我认为员工 a 的奖金应该比 b 高！”

Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。

每位员工奖金最少为100元，且必须是整数。

输入格式

第一行包含整数n,m，分别表示公司内员工数以及参会代表数。

接下来 m 行，每行 2 个整数 a,b，表示某个代表认为第 a 号员工奖金应该比第 bb 号员工高。

输出格式

若无法找到合理方案，则输出“Poor Xed”；

否则输出一个数表示最少总奖金。

数据范围

1≤n≤10000,
1≤m≤20000

输入样例：

2 1
1 2

输出样例：

201

代码：

/* 差分约束求最长路，根据边权不同可分以下三类： 不知道是否有解的情况下： 边权无限制，用 SPFA，最坏 O(nm) ，正环则无解 边权非负，对 SCC 缩点变 DAG 后按拓扑序递推，稳定O(n+m)，一个连通分量内部应该边权都是0，否则就存在正环，无解； 边权为正，如果不存在拓扑序就无解，所以用拓扑就可以 最长路负环和零环是可以的，但拓扑排序只能判断是否有环 对于DAG，最短路还是最长路都可以拓扑 */
#include <bits/stdc++.h>
using namespace std;

const int N = 10010, M = 20010;

int n, m;
int h[N], e[M], ne[M], idx;
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 != -1; 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 u = 0; u < n; u++) // 拓扑序遍历即可求最长路
        {
    
            int j = q[u];
            for (int i = h[j]; i != -1; i = ne[i])
            {
    
                dist[e[i]] = max(dist[e[i]], dist[j] + 1);
            }
        }
        int res = 0;
        for (int i = 1; i <= n; i++)
            res += dist[i];

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

    return 0;
}