「笔记」负环与差分约束（例题）

P1993 小 K 的农场

查分约束的主要思想在于建边。

观察 $n$ 个未知数组成的不等式组：

给定 $n$ 个数和 $m$ 个约束条件（如 $x_i - x_j \leq c$），求一组解。

约束条件可以转化为：

$x_i \leq c + x_j$

发现和最短路的更新（$dis_i \leq w + dis_j$）类似，所以可以转化为最短路问题。

根据题意分别建边：

1. a -> b len=-c
2. b -> a len=c
3. • a -> b len=0
   • b -> a len=0

主要在于第三种情况，分别按大于等于，小于等于建边。

会有多种解，求最小的那个，所以要建一个 $0$ 号节点，向每个点连一条长度为 $0$ 的边。

然后跑 SPFA，如果一个点加入队列 $n + 1$ 次，则判定为有负环，无解。

但是，我 TLE 了三个点，不知道为什么，吸氧就可以过。。。

代码：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

const int N = 5e3 + 10; 

struct edge{
	int to, dis;
};

int n, m, t, a, b, c;
int dis[N];
bool vis[N];
int cnt[N];
vector <edge> g[N];
queue <int> q;

bool spfa(){
	
	memset(dis, 0x3f, sizeof(dis));
	
	vis[0] = 1;
	dis[0] = 0;
	cnt[0]++;
	q.push(0);
	while(!q.empty()){
		t = q.front();
		q.pop();
		vis[t] = 0;
		for(int i = 0; i < g[t].size(); i++){
			if(dis[t] + g[t][i].dis < dis[g[t][i].to]){
				dis[g[t][i].to] = dis[t] + g[t][i].dis;
				cnt[g[t][i].to]++;
				if(cnt[g[t][i].to] == n){
					return 0;
				}
				if(!vis[g[t][i].to]){
					vis[g[t][i].to] = 1;
					q.push(g[t][i].to);
				}
			}
		}
	}
	return 1;
}

int main(){
	
	scanf("%d%d", &n, &m);
	
	while(m--){
		scanf("%d", &t);
		if(t == 1){
			scanf("%d%d%d", &a, &b, &c);
			g[a].push_back(edge{b, -c});
		}
		if(t == 2){
			scanf("%d%d%d", &a, &b, &c);
			g[b].push_back(edge{a, c});
		}
		if(t == 3){
			scanf("%d%d", &a, &b);
			g[a].push_back(edge{b, 0});
			g[b].push_back(edge{a, 0});
		}
	}
	
	for(int i = 1; i <= n; i++){
		g[0].push_back(edge{i, 0});
	}
	
	if(spfa()){
		puts("Yes");
	}else{
		puts("No");
	}
	
	
	return 0;
}

自己电脑测 $842 ms$，但一直过不了。

vector 的部分优化了一下，过了：

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>

using namespace std;

const int N = 5e3 + 10; 

struct edge{
	int to, dis;
};

int n, m, t, a, b, c, tp;
int dis[N];
bool vis[N];
int cnt[N];
vector <edge> g[N];
queue <int> q;

bool spfa(){
	
	memset(dis, 0x3f, sizeof(dis));
	
	vis[0] = 1;
	dis[0] = 0;
	cnt[0]++;
	q.push(0);
	while(!q.empty()){
		t = q.front();
		q.pop();
		vis[t] = 0;
		for(int i = 0; i < g[t].size(); i++){
			tp = g[t][i].to;
			if(dis[t] + g[t][i].dis < dis[tp]){
				dis[tp] = dis[t] + g[t][i].dis;
				cnt[tp]++;
				if(cnt[tp] == n){
					return 0;
				}
				if(!vis[tp]){
					vis[tp] = 1;
					q.push(tp);
				}
			}
		}
	}
	return 1;
}

int main(){
	
	scanf("%d%d", &n, &m);
	
	while(m--){
		scanf("%d", &t);
		if(t == 1){
			scanf("%d%d%d", &a, &b, &c);
			g[a].push_back(edge{b, -c});
		}
		if(t == 2){
			scanf("%d%d%d", &a, &b, &c);
			g[b].push_back(edge{a, c});
		}
		if(t == 3){
			scanf("%d%d", &a, &b);
			g[a].push_back(edge{b, 0});
			g[b].push_back(edge{a, 0});
		}
	}
	
	for(int i = 1; i <= n; i++){
		g[0].push_back(edge{i, 0});
	}
	
	if(spfa()){
		puts("Yes");
	}else{
		puts("No");
	}
	
	
	return 0;
}

？？？？？

「SCOI2011」糖果

这一题的建边比上一题复杂一些。

因为此题糖果数均为整数，所以 $<$ 就建长度为 $0$ 的边，$\leq$ 就建长度为 $1$ 的边。

如果不是整数，则 $<$ 就建长度为 $inf$ 的边，$inf$ 为一个极小的数。

1. • a -> b len=0
   • b -> a len=0
2. a -> b len=1
3. b -> a len=0
4. b ->a len=1
5. a -> b len=0

注意要开 long long。

whk 比较忙，有空再来补充。