奖金

差分约束 拓扑排序 T3 信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn) 由于无敌的凡凡在2005年世界英俊帅气男总决选中胜出，Yali Company总经理Mr.Z心情好，决定给每位员工发奖金。公司决定以每个人本年在公司的贡献为标准来计算他们得到奖金的多少。

于是Mr.Z下令召开m方会谈。每位参加会谈的代表提出了自己的意见：“我认为员工a的奖金应该比b高！”Mr.Z决定要找出一种奖金方案，满足各位代表的意见，且同时使得总奖金数最少。每位员工奖金最少为100元。

输入

第一行两个整数n,m，表示员工总数和代表数；

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

输出

若无法找到合理方案，则输出“Poor Xed”；否则输出一个数表示最少总奖金。

输入样例

2 1
1 2

输出样例

201

数据规模

80％的数据满足：n≤1000，m≤2000；

100％的数据满足：n≤10000，m≤20000。

思路

是一个差分约束问题, 我们可以用

• SPFA $O(nm)$
• tarjan $O(n+m)$ 当只有非负边时 这里还可以使用拓扑排序+DP的做法, 只有当权值 大于0 时可以使用, 复杂度为 $O(n+m)$ 。

先做一遍拓扑排序, 然后按照拓扑排序的方案来DP求最长路即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 1e4 + 10, M = 4e4 + 10;
int n, m;
int q[N], money[N], res;
int h[N], ne[M], e[M], idx;
int din[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 (!din[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 (--din[j] == 0)
                q[++tt] = j;
        }
    }
    if (tt < n - 1)
        return false;
    return true;
}
 
int main()
{
    memset(h, -1, sizeof h);
    memset(money, 0x3f, sizeof money);
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(b, a);
        din[a]++;
    }
    bool flag = topsort();
    if (!flag)
        cout << "Poor Xed";
    else
    {
        for (int i = 1; i <= n; i++)
            money[i] = 100;
        for (int i = 0; i < n; i++)
        {
            int j = q[i];
            for (int k = h[j]; ~k; k = ne[k])
                money[e[k]] = max(money[e[k]], money[j] + 1);
        }
        for (int i = 1; i <= n; i++)
            res += money[i];
        cout << res << endl;
    }
 
    return 0;
}