题目描述

幼儿园里有 N个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。

但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K个要求。

幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
输入格式

输入的第一行是两个整数 N,K。

接下来 K行，表示分配糖果时需要满足的关系，每行 3 个数字 X,A,B。

如果 X=1．表示第 A 个小朋友分到的糖果必须和第 B个小朋友分到的糖果一样多。
如果 X=2，表示第 A 个小朋友分到的糖果必须少于第 B个小朋友分到的糖果。
如果 X=3，表示第 A 个小朋友分到的糖果必须不少于第 B个小朋友分到的糖果。
如果 X=4，表示第 A 个小朋友分到的糖果必须多于第 B个小朋友分到的糖果。
如果 X=5，表示第 A 个小朋友分到的糖果必须不多于第 B个小朋友分到的糖果。

小朋友编号从 1到 N。
输出格式

输出一行，表示老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 −1。
数据范围

1≤N<105,
1≤K≤105,
1≤X≤5,
1≤A,B≤N

样例

输入样例：

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

输出样例：

11

差分约束

Tip：
将差分约束中的每一个要求的值都看作图中的点，例如xi<=yj+ck，那么i和j是点，ck是边权

在求最短路时，如果有一条从a到b，权值为c的边，那么最终求得的最短路一定有：dist[b]<=dist[a]+c,这与差分约束的不等式是同一形式；如果还有后续点，那么一定可以继续放缩下去，最后得到dist[b]<=c1+c2+…+ck，而如果要求差分约束某个值的最大值（如果有a<1,a<5，那么结果一定是a<1），那么一定是求最大值的最小值，那么在放缩到最后，得到的就是这个值，也就是说i这个点求得的最短路的长度dist[i]就是xi可取到的最大值。
同理，在求最长路时，如果有一条从a到b，权值为c的边，那么最终求得的最长路一定有：dist[b]>=dist[a]+c,如果求差分约束某个值的最小值，就是i这个点求得的最长路的长度dist[i]就是xi可取到的最小值。

在求最短路的时候，如果出现了负环，那么会导致xi[HTML_REMOVED]xi，也就是出现了矛盾，也是无解。

在建立图后，可能会有某些孤立点没有约束，所以建图后一定可以走到所有的边，但不一定可以走到所有的点，所以要建立虚拟源点，使得从这个源点出发可以走到所有点，那么才能求得每个值的最长路或最短路。

下面回到题目，要挖掘题目中的差分约束的条件。并且问至少要准备多少糖果，那么就要把所有的条件都写作最长路中xi>=xj+ck的形式（表示从j到i连一条路,并且边权是ck,求最长路）
五个条件分别化作：
X=1：第 A 个小朋友分到的糖果必须和第 B个小朋友分到的糖果一样多。
A>=B,B>=A;(从B到A连一条权为0的边，从A到B连一条权为0的边)

X=2:第 A 个小朋友分到的糖果必须少于第 B个小朋友分到的糖果。
B>A也就是B>=A+1;(从A到B连一条权为1的边)

X=3:第 A 个小朋友分到的糖果必须不少于第 B个小朋友分到的糖果。
A>=B;(从B到A连一条权为0的边)

X=4:第 A 个小朋友分到的糖果必须多于第 B个小朋友分到的糖果。
A>B也就是A>=B+1;(从B到A连一条权为1的边)

X=5:第 A 个小朋友分到的糖果必须不多于第 B个小朋友分到的糖果。
B>=A;(从A到B连一条权为0的边)

且每一个小朋友都要分到糖果，那么每一个都有xi>=x0+1，也就是从虚拟源点0向每一个点连一条权为1的边，x0就是源点且dist[0]=0,且可以走到每个点，每条边。

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;

const int N=100010,M=3*N;

typedef long long LL;

int h[N],e[M],ne[M],w[M],idx;
LL dist[N];
int n,k;
int q[N],st[N],cnt[N];

void add(int a,int b,int c){
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
bool spfa(){
    //这里求最长路，顺便判断是否有正环
    //由于源点一定可以到达每个点，所以求负环因为不需要把所有点开始都加入
    //用队列判断正环，可能会超时，换成栈会快一点，因为栈是后进先出，所以路径每次都是一直向后走，但是队列是一层一层的走
    //但是栈不能随意换，如果不是求正环或负环，用栈会很慢
    memset(dist,-0x3f,sizeof dist);
    dist[0]=0;
    int hh=0,tt=0;
    q[tt++]=0;
    st[0]=1;
    while(hh!=tt){
        int t=q[--tt];//int t=q[hh++];
        //if(hh==N)   hh=0;
        st[t]=0;
        for(int i=h[t];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]<dist[t]+w[i]){
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n+1) return false;
                if(!st[j]){
                    q[tt++]=j;
                    //if(tt==N)   tt=0;
                    st[j]=1;
                }
            }
        }
    }
    return true;
}
int main(){
    cin>>n>>k;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)   add(0,i,1);
    while(k--){
        int x,a,b;
        cin>>x>>a>>b;
        if(x==1){
            add(a,b,0);
            add(b,a,0);
        }
        else if(x==2)
            add(a,b,1);
        else if(x==3)
            add(b,a,0);
        else if(x==4)
            add(b,a,1);
        else
            add(a,b,0);
    }
    if(!spfa()) cout<<-1<<endl;
    else{
        LL ans=0;
        for(int i=1;i<=n;i++)   ans+=dist[i];
        printf("%lld\n",ans);
    }
    return 0;
}