比较裸的差分约束……
- 当(k=1)，在(a,b)之间连一条边权为(0)的双向边
- 当(k=2)，从(a)向(b)连一条边权为(1)的边
- 当(k=3)，从(b)向(a)连一条边权为(0)的边
- 当(k=4)，从(b)向(a)连一条边权为(1)的边
- 当(k=5)，从(a)向(b)连一条边权为(0)的边
这里还有两个小剪枝，一个是如果(k=2)或(k=4)时，(a=b)，那么肯定无解；另一个是从(0)号虚拟节点向其他各节点连边时要反向循环，不然会( t{T})一个点,具体原因不明……
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int read(){
int k=0; char c=getchar();
for(;c<'0'||c>'9';) c=getchar();
for(;c>='0'&&c<='9';c=getchar())
k=k*10+c-48;
return k;
}
struct zzz{
int t,len,nex;
}e[200010<<1]; int head[100010],tot;
void add(int x,int y,int z){
e[++tot].t=y; e[tot].len=z;
e[tot].nex=head[x]; head[x]=tot;
}
int dis[100010],inq[100010];
bool vis[100010];
long long ans;
int main(){
int n=read(),k=read();
for(int i=1;i<=k;i++){
int k=read(),x=read(),y=read();
if(k==1) add(x,y,0), add(y,x,0);
if(k==2){
if(x==y){ //剪枝1
cout<<-1; return 0;
}
add(x,y,1);
}
if(k==3) add(y,x,0);
if(k==4){
if(x==y){ //剪枝1
cout<<-1; return 0;
}
add(y,x,1);
}
if(k==5) add(x,y,0);
}
for(int i=n;i>=1;i--) add(0,i,1); //剪枝2
memset(dis,1277,sizeof(dis));
queue <int> q; q.push(0); vis[0]=1; dis[0]=0;
while(!q.empty()){
int k=q.front(); q.pop(); vis[k]=0;
for(int i=head[k];i;i=e[i].nex){
if(dis[e[i].t]<dis[k]+e[i].len){
dis[e[i].t]=dis[k]+e[i].len;
if(!vis[e[i].t]){
if(inq[e[i].t]==n-1){
cout<<-1; return 0;
}
inq[e[i].t]++;
q.push(e[i].t), vis[e[i].t]=1;
}
}
}
}
for(int i=1;i<=n;i++) ans+=dis[i];
cout<<ans;
return 0;
}