懒得复制，戳我戳我
Solution:
- 首先考虑(X=1)的情况，我们其实只用用一下并查集把相等的点合为一个点
- 然后后面的四个式子我们就可以用差分约束了，就拿(X=2)的情况来说吧，我们用(S[i])表示(i)号小朋友要拿多少糖果，如果X=2， 表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果，我们就可以写出式子(S[A]<S[B])，等价于(S[A]+1<=S[B])，这样我们就可以从(A)向(B)连一条权值为(1)的边。另外，如果是(S[A]<=S[B])，等价于(S[A]+0<=S[B])，连一条(0)边就可以
- 还要注意的就是，数据有可能为几个联通块，所以我们要将没有进行过SPFA/Dijkstra的边为初始点开始单元最长路，还有要在最长路操作中注意判断正环，有正环输出(-1)
- SPFA/Dijkstra里面不要memset，会超时到死，可以传递一个下表表示这是哪一次开始SPFA/Dijkstra，这样就不会了
（就是因为这个错误我TLE的好惨）
不过从5000ms到88ms超级爽啊
1. void SPFA(int k,int cs){}
2. vis[k]=cs;
3. if(vt[v]!=cs)TT[v]=1,vt[v]=cs;
else{
TT[v]++; if(TT[v]==n){wr=true;return;}
}
Code:
//It is coded by Ning_Mew on 3.28
#include<cmath>
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define LL long long
#define RG register
using namespace std;
const int maxn=1e5+10;
int n,K;
int color[maxn];
int head[maxn],cnt=0;
struct Edge{
int nxt,to;LL dis;
}edge[maxn];
int ct=0;
LL dist[maxn],ans=0;
bool wr=false,be[maxn];
struct Pro{
int pl,x,y;
}pro[maxn];
int read(){
int x=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x;
}
inline void add(int from,int to,LL dis){
edge[++cnt].nxt=head[from];
edge[cnt].to=to;
edge[cnt].dis=dis;
head[from]=cnt;
}
inline int getf(int k){
if(color[k]==k)return color[k];
color[k]=getf(color[k]);
return color[k];
}
int TT[maxn],vt[maxn],vis[maxn],Q[maxn+7],front=0,tail=1,again=0;
inline void SPFA(int k,int cs){
front=0;tail=1;
Q[front]=k;
vis[k]=cs; dist[k]=1;be[k]=false;
while(front<tail+maxn*again){
if(front>maxn){front%=maxn;again--;}
int u=Q[front];front++;vis[u]=cs-1;
for(int i=head[u];i!=0;i=edge[i].nxt){
int v=edge[i].to;be[v]=false;
if(dist[v]<dist[u]+edge[i].dis){
dist[v]=dist[u]+edge[i].dis;
if(vis[v]!=cs){
if(dist[v]>dist[ Q[front] ]&&front-1>=0){
front--;Q[front]=v;
}else{
if(tail>maxn){again++;tail%=maxn;}
Q[tail]=v;tail++;
}
//if(tail>maxn){again++;tail%=maxn;}
//Q[tail]=v;tail++;
vis[v]=cs;
if(vt[v]!=cs)TT[v]=1,vt[v]=cs;
else{
TT[v]++; if(TT[v]==n){wr=true;return;}
}
}
}
}
}
}
int main(){
//scanf("%d%d",&n,&K);
n=read();K=read();
for(int i=1;i<=n;i++)color[i]=i;
for(RG int i=1;i<=K;i++){
int pl,x,y;
pl=read();x=read();y=read();
//scanf("%d%d%d",&pl,&x,&y);
if(pl==1){
int color1=getf(x),color2=getf(y);
if(color1!=color2)color[color1]=color2;
continue;
}
pro[++ct].pl=pl;pro[ct].x=x;pro[ct].y=y;
}
memset(be,false,sizeof(be));
for(RG int i=1;i<=n;i++){
color[i]=getf(i);
//cout<<i<<" color="<<color[i]<<endl;
be[color[i]]=true;
}
for(RG int i=1;i<=ct;i++){
int A=color[pro[i].x],B=color[pro[i].y];
if(pro[i].pl==2){add(A,B,1);continue;}
if(pro[i].pl==3){add(B,A,0);continue;}
if(pro[i].pl==4){add(B,A,1);continue;}
if(pro[i].pl==5){add(A,B,0);continue;}
}
memset(dist,-0x5f,sizeof(dist));
int INF=dist[0],cs=0;;
for(RG int i=1;i<=n;i++){
if(be[i]){cs++;SPFA(i,cs);}
//cout<<i<<endl;
if(wr==true){printf("-1
");return 0;}
}
for(RG int i=1;i<=n;i++){
if(dist[color[i]]!=INF)ans+=dist[color[i]];
}
printf("%lld
",ans);
return 0;
}