【差分约束系统】糖果

图论

题目传送门：CodeVS2404

这是一道很典型的差分约束系统

由于是我的第一道差分约束系统，先来科普一下

差分约束系统

仅限于我的理解

差分约束系统可以用来求解一类不等式的解

例如：

a-b>=x; b-c>=y;

显然可以得到 a-c>=x+y

那么为了求解这类东西可以将a-b>=x转换为从a点向b点连一条长度为x的边（这里连边的方向什么都可以随题意改变，符号也可以改变）

建完图以后SPFA之类的就可以求解了

回到题目

于是对各类情况分类讨论建图，

这里有两个注意点：

----如果a==b，那么就a向b连一条长度为0的边，b向a也连一条长度为0的边

----如果a!=b， 不要忘了特判不能是一个小朋友，否则自环不好处理

然后为了使整个图连通起来，可以建一个源点S，由S向所有点连边，边长为1（因为每个人至少1颗糖）

也可以先把所有点都放到队列里

然后SPFA

此题有个坑点，加到队列时如果逆序似乎会T一个点。。。

详见代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define LL long long
LL n,m,tot,t,w,now,x,y,z,ans;
LL head[100030],q[100030],vis[100030],cir[100030],dis[100030];
struct edge{
	LL u,v,dis,last;
}
e[400030];
void add(LL x,LL y,LL z){
	tot++;
	e[tot].u=x;
	e[tot].v=y;
	e[tot].dis=z;
	e[tot].last=head[x];
	head[x]=tot;
}
bool spfa(){
	q[1]=0;
	vis[0]=1;
	cir[0]=1;
	t=0;
	w=1;
	while (t!=w){
		t=t%(n+10)+1;
		now=q[t];
		for (int i=head[now];i;i=e[i].last)
			if (dis[e[i].v]<dis[now]+e[i].dis){
				dis[e[i].v]=dis[now]+e[i].dis;
				if (++cir[e[i].v]>n) return 0;
				if (!vis[e[i].v]){
					vis[e[i].v]=1;
					w=w%(n+10)+1;
					q[w]=e[i].v;
				}
			}
		vis[now]=0;
	}
	return 1;
}
int main(){
	scanf("%lld%lld",&n,&m);
	
	for (int i=n;i>0;i--) add(0,i,1);
	
	for (int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
		if (x==1){ add(y,z,0); add(z,y,0); }
		if (x==2){
			if (y==z){ printf("-1\n"); return 0; }
			add(y,z,1);
		}
		if (x==3) add(z,y,0);
		if (x==4){
			if (y==z){ printf("-1\n"); return 0; }
			add(z,y,1);
		}
		if (x==5) add(y,z,0);
	}
	
	if (!spfa()){
		printf("-1\n");
		return 0;
	}
	for (int i=1;i<=n;i++) ans+=dis[i];
	printf("%lld\n",ans);
	
	return 0;
}