【题目描述】
幼儿园里有$N$个小朋友，$lxhgww$老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，$lxhgww$需要满足小朋友们的$K$个要求。幼儿园的糖果总是有限的，$lxhgww$想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
神仙幼儿园
【输入格式】
输入的第一行是两个整数$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$个小朋友分到的糖果；
【输出格式】
输出一行，表示$lxhgww$老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出$-1$。
$N\leq 100000$$K\leq 100000$$1\leq X\leq 5$$1\leq A, B\leq N$
差分约束模版题
关于差分约束
差分约束系统是用于解决这样一类问题的：给你$n$个形如$x-y\le z$的不等式，求是否有解及符合条件的一组解
对于此类问题处理方式就是对于每个$x-y\le z$, 连一条从y到x，边权为z的有向边。如果是形如$x-y\ge z$的不等式，也可以将它转换成$y-x \le -z$来连边。
如果给出了一组$x=y$的等式，可以转化为$0 \le x-y \le 0$即连一条$x, y$之间的边权为$0$的无向边。
最后从$0$号点向每个点连一条边权为$0$的有向边，或者如果每个数至少要是$1$就连边权为$1$的边。
然后从$0$号点开始跑SPFA，如果有负环则无解，否则$dis[1]$到$dis[n]$就是对应的一组解。
【代码】
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| #include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define re register
using namespace std;
typedef long long ll;
ll n, m, sum;
ll head[1000005], to[1000005], pre[1000005], val[1000005], len;
ll dis[1000005], cnt[1000005];
bool vis[1000005];
ll read() {
ll ret = 0;
char ch = getchar();
while (ch < '0' || ch > '9') ch = getchar();
while (ch >= '0' && ch <= '9') {
ret = ret * 10 + ch - '0';
ch = getchar();
}
return ret;
}
void insert(ll u, ll v, ll w) {
len++;
to[len] = v, pre[len] = head[u], val[len] = w, head[u] = len;
}
queue<ll> q;
bool SPFA() {
q.push(0);
vis[0] = 1;
while (!q.empty()) {
ll c = q.front();
q.pop();
vis[c] = 0;
if (cnt[c] == n - 1) return false;
cnt[c]++;
for (re ll i = head[c]; i != 0; i = pre[i]) {
if (dis[c] + val[i] > dis[to[i]]) {
dis[to[i]] = dis[c] + val[i];
if (!vis[to[i]]) {
vis[to[i]] = 1;
q.push(to[i]);
}
}
}
}
return true;
}
int main() {
n = read(), m = read();
for (re ll i = 1; i <= m; i++) {
ll ch, a, b;
ch = read();
a = read(), b = read();
switch (ch) {
case 1: insert(b, a, 0), insert(a, b, 0); break;
case 2: {
insert(a, b, 1);
if (a == b) {
cout << -1 << endl;
return 0;
}
break;
}
case 3: insert(b, a, 0); break;
case 4: {
if (a == b) {
cout << -1 << endl;
return 0;
}
insert(b, a, 1);
break;
}
case 5: insert(a, b, 0); break;
}
}
for (re ll i = n; i >= 1; i--) {
insert(0, i, 1);
}
q.push(0);
vis[0] = 1;
while (!q.empty()) {
ll c = q.front();
q.pop();
vis[c] = 0;
for (re ll i = head[c]; i != 0; i = pre[i]) {
if (dis[c] + val[i] > dis[to[i]]) {
dis[to[i]] = dis[c] + val[i];
if (!vis[to[i]] && cnt[to[i]] < n) {
vis[to[i]] = 1;
cnt[to[i]]++;
q.push(to[i]);
} else if (cnt[to[i]] >= n) {
cout << -1 << endl;
return 0;
}
}
}
}
for (int i = 1; i <= n; i++) sum += dis[i];
cout << sum << endl;
return 0;
}
|
