首页 > 编程学习 > 洛谷 P3275 [SCOI2011]糖果(差分约束,tarjan强连通分量,scc)

[SCOI2011]糖果

题目描述

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

输入格式

输入的第一行是两个整数 N N N K K K。接下来 K K K 行,表示这些点需要满足的关系,每行 3 3 3 个数字, X X X A A A B B B

  • 如果 X = 1 X=1 X=1, 表示第 A A A 个小朋友分到的糖果必须和第 B B B 个小朋友分到的糖果一样多;
  • 如果 X = 2 X=2 X=2, 表示第 A A A 个小朋友分到的糖果必须少于第 B B B 个小朋友分到的糖果;
  • 如果 X = 3 X=3 X=3, 表示第 A A A 个小朋友分到的糖果必须不少于第 B B B 个小朋友分到的糖果;
  • 如果 X = 4 X=4 X=4, 表示第 A A A 个小朋友分到的糖果必须多于第 B B B 个小朋友分到的糖果;
  • 如果 X = 5 X=5 X=5, 表示第 A A A 个小朋友分到的糖果必须不多于第 B B B 个小朋友分到的糖果;

输出格式

输出一行,表示 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 ≤ 100 N\leq100 N100

对于 100 % 100\% 100% 的数据,保证 N ≤ 100000 N\leq100000 N100000

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


upd 2022.7.6 \text{upd 2022.7.6} upd 2022.7.6:新添加 21 21 21 组 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]+w
	
2、如果图中没有 正环, 说明有解。
3、如果用 spfa 求最长距离,这里会TLE.
4、但是它边权只有 00 或 11,考虑这个图有什么特殊性质。
	先缩点,每个 SCC 内部如果出现了一条 uu 到 vv 的边权为 11,根据 SCC 的定义,
	一定还存在一条 vv 到 uu 的路径,由于边权 \geq 0≥0,所以一定会出现一个正权环,
	则这个差分约束系统无解。否则的话,发现 SCC 内部变量取值一定是相同的,
	那么问题变成了一个 DAG 上最长路,拓扑排序即可	
#include <bits/stdc++.h>
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时, 记录scc
	if(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<int> 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;
}
Copyright © 2010-2022 dgrt.cn 版权所有 |关于我们| 联系方式