本文共 2709 字，大约阅读时间需要 9 分钟。

拓扑排序(差分约束) - Reward - HDU 2647

题意：

格林剧团发工资的时候又到辣，格林剧团来到了圣巢，他们入乡随俗，将工资用圣巢的货币–吉欧来结算。格林团长决定每个人的最低工资是888吉欧，同时有些工人希望自己的工资要比其他某个人的高。格林团长希望在尽可能的少发工资的同时满足其他所有人的需求。请你帮帮格林团长吧，格林团长会邀请你与其在剧团内共舞一场猩红仪式。

Input

题目包含多组输入，第一行输入两个整数n,m，分别表示工人的数量与需求的个数。 接下来m行，每一行都包含两个整数a和b，表示a的工资必须比b的工资高

Output

对于每一组输入，输出格林团长最少花费的吉欧数量。如果格林团长不能满足所有人的需求，输出-1.

Sample Input

2 11 22 21 22 1

Sample Output

1777-1

分析：

$差分约束问题。$

$若A要求比B高，即要求A>B，即A\ge B+1，我们对应建边A->B，边权为1。$

$最终要求最小值，跑最长路。$

$由于边权恒大于0，故我们可以用拓扑排序求最短路，时间复杂度为O(n+m)。$

$若存在正环或孤立点，拓扑排序得到的元素数量将会小于n。$$以此来判断是否有解。$

$若有解，由于要求所有人薪水不低于888，即对任意的i，dis[i]\ge 0+888，$

$我们可以建立虚拟源点0号点，dis[0]=0，且0号点与其他点之间均建立一条边权为888的边。$

$等价于我们直接初始化dis数组为888，这样可以省掉建立虚拟源点的过程。$

$接着按照阶段跑最长路即可。$

代码：

#include<cstdio>#include<algorithm>#include<cstring>using namespace std;const int N=10010, M=20010;int n,m;int e[M],ne[M],h[N],idx;int dis[N];int d[N];int q[N],hh,tt=-1;void add(int a,int b){       e[idx]=b,ne[idx]=h[a],h[a]=idx++;}bool topsort(){       hh=0,tt=-1;    for(int i=1;i<=n;i++)        if(!d[i])            q[++tt]=i;                while(hh<=tt)    {           int u=q[hh++];                for(int i=h[u];~i;i=ne[i])        {               int j=e[i];            d[j]--;            if(!d[j]) q[++tt]=j;        }    }        return tt==n-1;}   int cal(){       for(int i=1;i<=n;i++) dis[i]=888;  //初始值        for(int i=0;i<n;i++)    //遍历拓扑序,跑最长路    {           int u=q[i];        for(int j=h[u];~j;j=ne[j])        {               int k=e[j];            dis[k]=max(dis[k],dis[u]+1);        }    }        int res=0;    for(int i=1;i<=n;i++) res+=dis[i];        return res;}int main(){       while(~scanf("%d%d",&n,&m))    {           idx=0;        memset(h,-1,sizeof h);        memset(d,0,sizeof d);                int a,b;        while(m--)        {               scanf("%d%d",&a,&b);            add(b,a);            d[a]++;        }                if(!topsort()) puts("-1");        else printf("%d\n",cal());    }        return 0;}