BZOJ2330 (糖果)[差分约束]

发表于 | 更新于 | | 阅读次数：

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=2330

差分约束题，差分约束理论见这篇博文

如果给出的不等式有”<=”也有”>=”，又该如何解决呢？很明显，首先需要关注最后的问题是什么，如果需要求的是两个变量差的最大值，那么需要将所有不等式转变成”<=”的形式，建图后求最短路；相反，如果需要求的是两个变量差的最小值，那么需要将所有不等式转化成”>=”，建图后求最长路。
引用自http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html

这题还需要注意自环，因为是求最长路，某些写法的spfa可能不会让正自环无限入队，从而导致无法正确判断这类正环的情况。

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
80
81
82
83
84
85
86
87
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
const int MAXN=100009;
typedef long long ll;
using namespace std;
int n,k;
vector<int> V[MAXN];
vector<int> E[MAXN];
queue<int> q;
int vis[MAXN];
int cnt[MAXN];
ll d[MAXN];
inline void add(int a,int b,int w) {
	V[a].push_back(b);
	E[a].push_back(w);
}
bool spfa() {
	for(int i=0;i<=n;i++) d[i]=-1;
	while(!q.empty()) q.pop();
	vis[0]=1;
	q.push(0);
	++cnt[0];
	d[0]=0;
	while(!q.empty()) {
		int now=q.front(),v; q.pop();
		for(int i=0;i<V[now].size();i++) {
			v=V[now][i];
			if(d[now]+E[now][i]>d[v]) {
				d[v]=d[now]+E[now][i];
				if(!vis[v]) {
					vis[v]=1;
					q.push(v);
					++cnt[v];
					if(cnt[v] > n) return 0;
				}
			}
		}
		vis[now]=0;
	}
	return 1;
}
int main() {
	int x,a,b;
	scanf("%d%d",&n,&k);
	for(int i=0;i<=n;i++) V[i].clear(),E[i].clear();
	for(int i=1;i<=k;i++) {
		scanf("%d%d%d",&x,&a,&b);
		if(x==1) {
			add(a,b,0);
			add(b,a,0);
		}
		else if(x==2) {
			add(a,b,1);
			if(a==b) {
				puts("-1");
				return 0;
			}
		}
		else if(x==3) {
			add(b,a,0);
		}
		else if(x==4) {
			add(b,a,1);
			if(a==b) {
				puts("-1");
				return 0;
			}
		}
		else if(x==5) {
			add(a,b,0);
		}
	}
	for(int i=1;i<=n;i++) add(0,i,1);
	bool flag=spfa();
	if(!flag) {
		puts("-1");
		return 0;
	}
	ll ans=0;
	for(int i=1;i<=n;i++) {
		ans+=d[i];
	}
	printf("%lld\n",ans);
}