P3275 [SCOI2011] 糖果（差分约束 + tarjan + 缩点 + 拓扑排序 + dp）

P3275 [SCOI2011] 糖果

放一个传送门
https://www.luogu.com.cn/problem/P3275

这道题看起来很像是差分约束 $+spfa$ 的模板题目，但是我们可以从数据范围发现，最坏情况下 $N\times K=10^{10}$ 。所以显然是不能用 $spfa$ 的。很惊奇地发现，网上大部分题解都是有问题的。（也可能是题目改过数据范围）

我们可以用差分约束 + $tarjan$ + 缩点 + 拓扑排序 + $dp$ 来完成这道题！

参考学习文章
差分约束
tarjan

——————————————————————————————————————

[SCOI2011] 糖果

题目描述

幼儿园里有 $N$ 个小朋友，$\text{lxhgww}$ 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，$\text{lxhgww}$ 需要满足小朋友们的 $K$ 个要求。幼儿园的糖果总是有限的，$\text{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$ 个小朋友分到的糖果；

输出格式

输出一行，表示 $\text{lxhgww}$ 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 $-1$。

样例 #1

样例输入 #1

5 7
1 1 2
2 3 2
4 4 1
3 4 5
5 4 5
2 3 5
4 5 1

样例输出 #1

11

提示

对于 $30\%$ 的数据，保证 $N\le 100$

对于 $100\%$ 的数据，保证 $N\le 100000$

对于所有的数据，保证 $K\le 100000,1\le X\le 5,1\le A,B\le N$

---

$\text{upd 2022.7.6}$：新添加 $21$ 组 Hack 数据。

——————————————————————————————————
下面来看具体代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const ll M = 2e5 + 10;
const ll inf = 1e9 + 5;ll n, m, a, b;vector<pair<ll,ll>>g[M];//老图//tarjan需要的
ll dfn[M];
ll low[M];
ll tot[M];//缩点后每个强连通分量的个数
ll idx = 1;//dfs的时间序
bitset<M>ins;//是否已经入栈
stack<int>stk;//tarjan的栈//缩点需要地
int number = 0;//代表每个强连通分量的id
ll belong[M];//每个点归属于哪个number的强连通分量//建新图
vector<pair<ll, ll>>newg[M];//缩点后的新图//拓扑需要的
ll in[M];//入度
//dp每个强连通分量
ll dp[M];void tarjan(int x)
{low[x] = dfn[x] = ++idx;stk.push(x);ins[x] = 1;for (auto& [w, y] : g[x]){if (dfn[y] == 0){tarjan(y);low[x] = min(low[x], low[y]);}else if (ins[y])low[x] = min(low[x], dfn[y]);}if (dfn[x] == low[x]){number++;//强连通分量标号belong[x] = number;//将内部节点进行归属ins[x] = 0;tot[number]++;while (stk.top() != x){ll ttt = stk.top();stk.pop();belong[ttt] = number;ins[ttt] = 0;tot[number]++;}stk.pop();//记得把x也踢出去}
}void solve()
{cin >> n >> m;for (int i = 1; i <= m; i++){int op;cin >> op >> a >> b;//进行差分约束，若看不懂请看上面推荐地学习参考if (op == 1){g[a].push_back({ 0,b });g[b].push_back({ 0,a });}else if (op == 2)g[a].push_back({ 1,b });else if (op == 3)g[b].push_back({ 0,a });else if (op == 4)g[b].push_back({ 1,a });elseg[a].push_back({ 0,b });}//tarjanfor (int i = 1; i <= n; i++)if (dfn[i] == 0)tarjan(i);//缩点建新图for (int x = 1; x <= n; x++){for (auto& [w, y] : g[x]){if (belong[x] == belong[y] && w != 0)//相当于是正环，一定无解{cout << -1 << '\n';return;}if (belong[x] != belong[y]){newg[belong[x]].push_back({ w,belong[y] });in[belong[y]]++;}}}//拓扑排序queue<int>q;for (int i = 1; i <= n; i++){if (in[i] == 0)//入度为0的才加入到队列中{q.push(i);dp[i] = 1;//}}while (q.size()){int ttt = q.front();q.pop();for (auto& [w, y] : newg[ttt]){in[y]--;dp[y] = max(dp[y], dp[ttt] + w);if (in[y] == 0)q.push(y);}}ll ans = 0;for (int i = 1; i <= number; i++)ans += dp[i] * tot[i];//一定记得乘上tot[i]代表这个强连通分量中的点数cout << ans << '\n';
}int main()
{std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);//cout << fixed << setprecision(4);int T = 1;//cin >> T;while (T--)solve();return 0;
}