【题目描述】
幼儿园里有$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; }
|