[SCOI2011]糖果

题目描述

幼儿园里有 NNN 个小朋友，lxhgww\text{lxhgww}lxhgww 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候，lxhgww\text{lxhgww}lxhgww 需要满足小朋友们的 KKK 个要求。幼儿园的糖果总是有限的，lxhgww\text{lxhgww}lxhgww 想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入格式

输入的第一行是两个整数 NNN，KKK。接下来 KKK 行，表示这些点需要满足的关系，每行 333 个数字，XXX，AAA，BBB。

• 如果 X=1X=1X=1， 表示第 AAA 个小朋友分到的糖果必须和第 BBB 个小朋友分到的糖果一样多；
• 如果 X=2X=2X=2， 表示第 AAA 个小朋友分到的糖果必须少于第 BBB 个小朋友分到的糖果；
• 如果 X=3X=3X=3， 表示第 AAA 个小朋友分到的糖果必须不少于第 BBB 个小朋友分到的糖果；
• 如果 X=4X=4X=4， 表示第 AAA 个小朋友分到的糖果必须多于第 BBB 个小朋友分到的糖果；
• 如果 X=5X=5X=5， 表示第 AAA 个小朋友分到的糖果必须不多于第 BBB 个小朋友分到的糖果；

输出格式

输出一行，表示 lxhgww\text{lxhgww}lxhgww 老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 −1-1−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%30\%30% 的数据，保证 N≤100N\leq100N≤100

对于 100%100\%100% 的数据，保证 N≤100000N\leq100000N≤100000

对于所有的数据，保证 K≤100000,1≤X≤5,1≤A,B≤NK\leq100000, 1\leq X\leq5, 1\leq A, B\leq NK≤100000,1≤X≤5,1≤A,B≤N

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

1、 这题是差分约束，最小化某两个变量的距离。对于约束条件 x[i]-x[j]<=w，转化为x[j]>=x[i]-w；类比单源最长路径中的三角不等式 (d[v]>=d[u]+w, u->v)，连 i->j 边权=-w的边，代表d[j]不能小于d[i]+w2、如果图中没有 正环， 说明有解。
3、如果用 spfa 求最长距离，这里会TLE.
4、但是它边权只有 00 或 11，考虑这个图有什么特殊性质。先缩点，每个 SCC 内部如果出现了一条 uu 到 vv 的边权为 11，根据 SCC 的定义，一定还存在一条 vv 到 uu 的路径，由于边权 \geq 0≥0，所以一定会出现一个正权环，则这个差分约束系统无解。否则的话，发现 SCC 内部变量取值一定是相同的，那么问题变成了一个 DAG 上最长路，拓扑排序即可	

#include 
using namespace std;
typedef long long ll;
const int N = 1e5 + 10, M = 2e5 + 10;;
const int inf = 0x3f3f3f3f;
int head[N], ver[M], edge[M], Next[M];
int head1[N], ver1[M], edge1[M], Next1[M];
int n, m, tot, tot1;int stk[N], instk[N], top;	//栈
int dfn[N], low[N], num;
int scc[N], siz[N], cnt;
int in_degree[N];	//缩点的入度
int dis[N];			//缩点后的图，到某一点路径上，所有点权值的最大值void add(int x, int y, int z)
{ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;	
}void add1(int x, int y, int z)	//缩点重新就建图
{ver1[++tot1] = y, edge1[tot1] = z, Next1[tot1] = head1[x], head1[x] = tot1;	
}void tarjan(int x)
{dfn[x] = low[x] = ++num;stk[++top] = x, instk[x] = 1;for(int i = head[x]; i; i = Next[i]){int y = ver[i];if(!dfn[y])	//y尚未访问{tarjan(y);low[x] = min(low[x], low[y]);}else if(instk[y]){	//y已经访问并且在栈中low[x] = min(low[x], dfn[y]);}}//离x时， 记录sccif(dfn[x] == low[x]) // 若x是scc的根{int y; ++cnt;do{y = stk[top--]; instk[y] = 0;scc[y] = cnt; // scc编号++siz[cnt];}while(y != x);}
}void bfs()
{queue q;for(int i = 1; i <= cnt; ++i){if(in_degree[i] == 0){q.push(i);dis[i] = 1;}}while(q.size()){int x = q.front(); q.pop();for(int i = head1[x]; i; i = Next1[i]){int y = ver1[i], z = edge1[i];if(dis[y] < dis[x] + z){dis[y] = dis[x] + z;}in_degree[y]--;if(in_degree[y] == 0)q.push(y);}}ll ans = 0;for(int i = 1; i <= cnt; ++i){//	printf("dis[%d] = %d, siz[%d] = %d\n", i, dis[i], i, siz[i]);ans += (ll)siz[i] * dis[i];}printf("%lld\n", ans);
}int main()
{scanf("%d%d", &n, &m);int op, x, y;for(int i = 0; i < m; ++i){scanf("%d%d%d", &op, &x, &y);if(op == 1){add(x, y, 0), add(y, x, 0);	}else if(op == 2){add(x, y, 1);}else if(op == 3){add(y, x, 0);	}else if(op == 4){add(y, x, 1);}else{add(x, y, 0);}}for(int i = 1; i <= n; ++i){if(!dfn[i])tarjan(i);}bool flag = false;for(int x = 1; x <= n; ++x){for(int i = head[x]; i; i = Next[i]){int y = ver[i], z = edge[i];if(scc[x] != scc[y]){add1(scc[x], scc[y], z);in_degree[scc[y]]++;}else{if(z != 0){flag = true;break;}}}}if(flag){printf("-1\n");return 0;}bfs();return 0;
}