Acwing 1169.糖果
题意
幼儿园里有 N 个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。
但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K 个要求。
幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
思路
先将所有小朋友获得的糖果设成变量，即我们有 N 个变量，然后根据 K 个要求写出不等式，因为求的是最小值，所以应该用最大路的差分约束模型。
然后考虑一个问题：是否存在一个源点，它可以到达所有的边，我们可以发现，如果只用上述的 K 个不等式，是不存在这样的点的，所以我们建立一个虚拟源点 0，所有的变量都满足 x i > 0 即 x i > = 0 + 1，所以只需要在虚拟源点和所有点之间连一条长度为1 的边即可。
接下来套用差分约束的最长路模型即可。
代码
// Author：zzqwtcc // Problem: 糖果 // Contest: AcWing // Time：2021-10-28 22:29:13 // URL: https://www.acwing.com/problem/content/1171/ // Memory Limit: 64 MB // Time Limit: 1000 ms #include<bits/stdc++.h> #include<unordered_map> // #define int long long #define INF 0x3f3f3f3f #define INFL 0x3f3f3f3f3f3f3f3f #define mod 1000000007 #define MOD 998244353 #define rep(i, st, ed) for (int (i) = (st); (i) <= (ed);++(i)) #define pre(i, ed, st) for (int (i) = (ed); (i) >= (st);--(i)) // #define debug(x,y) cerr << (x) << " == " << (y) << endl; #define endl '\n' using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int> PII; template<typename T> inline T gcd(T a, T b) { return b ? gcd(b, a % b) : a; } template<typename T> inline T lowbit(T x) { return x & -x; } template<typename S,typename T>void debug(S s, T t){cerr << s << " == " << t << endl;} template<typename T>void debug(T t){cerr << t << endl;} template<typename T>void debug(T t[],int st,int ed){for(int i = st; i <=ed;++i){cerr << t[i] << " ";}cerr << endl;} template<typename T>void debug(const vector<T>&t){for(int i =0 ; i < t.size();++i)cerr << t[i] << " ";cerr << endl;} // template<typename T> T qmi(T a, T b = mod - 2, T p = mod) { T res = 1; b %= (p - 1 == 0 ? p : p - 1); while (b) { if (b & 1) { res = (LL)res * a % p; }b >>= 1; a = (LL)a * a % p; }return res % mod; } const int N = 1e5 + 10, M = 5 * N; int n, k; int h[N],e[M],ne[M],w[M],idx; int cnt[N], d[N]; bool st[N]; void add(int a,int b, int c){ e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++; } bool spfa(){ memset(d,-0x3f,sizeof d); stack<int>q; q.push(0); d[0] = 0; while(q.size()){ int u = q.top(); q.pop(); st[u] = false; for(int i = h[u]; ~i; i = ne[i]){ int j = e[i]; int dis = w[i]; if(d[j] < d[u] + dis){ d[j] = d[u] + dis; cnt[j] = cnt[j] + 1; if(cnt[j] >= n + 1)return false; if(!st[j]){ st[j] = true; q.push(j); } } } } return true; } void solve() { cin >> n >> k; memset(h,-1,sizeof h); while(k--){ int x,a,b;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); else if(x == 3)add(b,a,0); else if(x == 4)add(b,a,1); else add(a,b,0); } for(int i = 1; i <= n;++i)add(0,i,1); if(spfa()){ LL res = 0; for(int i = 1; i <= n;++i){ res += d[i]; } cout << res << endl; } else puts("-1"); } signed main() { //int _; cin >> _; //while (_--) solve(); return 0; }
