Description

幼儿园里有N个小朋友，lxhgww老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的，lxhgww想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

Input

输入的第一行是两个整数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个小朋友分到的糖果；

Output

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

Sample Input

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

Sample Output

11

【数据范围】

对于30%的数据，保证 N<=100 对于100%的数据，保证 N<=100000 对于所有的数据，保证 K<=100000，1<=X<=5，1<=A, B<=N

分析

很明显的差分约束系统。 由于是求最小值，所以就要把所有不等式都转换成x-y>=k的形式然后连一条y->x权值为k的边。 后四个操作都很简单，关键是第一个操作。 那么我们就可以把A=B转换成A-B>=0且B-A>=0然后跑最长路最后统计就好啦。 还有就是判断负权（最短路）或正权（最长路）回路的问题，若一个点被松弛了n次以上则为有回路。 有一个很神奇的地方就是加起点到所有点的边的时候要倒着加不然就会T（我也不造为毛）

#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <vector> #include <queue> #include <cmath> #define N 100005 #define M 100005 using namespace std; struct NOTE { int to,val,next; }e[N*4]; int head[N*4],t[N],dis[N]; int temp; bool vis[N]; inline int read() { int x=0; int k=1; char ch; ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') k=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*k; } void add(int x,int y,int val) { e[++temp].to=y; e[temp].val=val; e[temp].next=head[x]; head[x]=temp; } int main() { int n,k; n=read(); k=read(); for(int i=1;i<=k;i++) { int x,a,b; x=read(); a=read(); b=read(); if(x==1) { add(a,b,0); add(b,a,0); } if(x==2) { if(a==b) { printf("-1\n"); return 0; } add(a,b,1); } if(x==3) { add(b,a,0); } if(x==4) { if(a==b) { printf("-1\n"); return 0; } add(b,a,1); } if(x==5) { add(a,b,0); } } for(int i=n;i>0;i--) add(0,i,1); long long ans=0; memset(vis,false,sizeof(vis)); memset(dis,0,sizeof(dis)); queue<int> Q; Q.push(0); t[0]++; while(!Q.empty()) { int now=Q.front(); Q.pop(); for(int i=head[now];i;i=e[i].next) { if(e[i].val+dis[now]>dis[e[i].to]) { if(!vis[e[i].to]) { Q.push(e[i].to); vis[e[i].to]=true; } t[e[i].to]++; if(t[e[i].to]>n) { printf("-1\n"); return 0; } dis[e[i].to]=e[i].val+dis[now]; } } vis[now]=false; } for(int i=1;i<=n;i++) ans+=dis[i]; printf("%lld\n",ans); }