P1993 小 K 的农场差分约束SPFA判断负环详细题解

题目传送门

题目大意

一共 $N$ 个点， $M$ 条边。

有 $3$ 种类型的边：

单向边：从点 $i$ 到点 $j$ 至少有 $c$ ，也就是 ai−aj≥c
单向边：从点 $i$ 到点 $j$ 至多有 $c$ ，ai−aj≤c
双向边：从点 $i$ 到点 $j$ 一样多，ai=aj

将这 $3$ 种边转换一下可以得到：

aj≤ai−c
ai≤aj+c
ai=aj+0 与 aj=ai+0

解题思路

判断负环

如果K的记忆冲突了，那么就说明有负环（小K绕晕了😵），输出 NO

如果K的记忆有至少1种情况没有冲突，那么就说明图中不存在负环，则输出 YES

// 判断负环
cnt[v] = cnt[u] + 1;
if (cnt[v] > n) {
	cout << "No\n"; // 有，就输出NO
	exit(0);
}


// 没有负环，在函数外输出YES
spfa(0);
cout << "Yes\n";
return 0;

处理 3 种边

$c$ 代表从某一点至某一点的边所需的花费。

对于第一种，从点 $i$ 到点 $j$ 至少有 $c$ ：

观察式子 aj≤ai−c 可得出从点 $i$ 到点 $j$ 花费为 $-c$

对于第二种，从点 $i$ 到点 $j$ 至多有 $c$ ：

观察式子 ai≤aj+c 可得出从点 $j$ 到点 $i$ 花费为 $c$

对于第三种，从点 $i$ 到 $j$ 数量一样，即 $c$ 为 $0$ ：

观察式子 ai=aj+0 与 aj=ai+0 可得出从点 $i/j$ 到点 $i/j$ 花费为 $0$ ，是一条双向边

for (int i = 1; i <= m; ++i) {
	int op; cin >> op;
	int u, v, w = 0;
	if (op == 1) {
		cin >> u >> v >> w;
		e[u].emplace_back(v, -w);
	} else if (op == 2) {
		cin >> u >> v >> w;
		e[v].emplace_back(u, w);
	} else {
		cin >> u >> v;
		e[u].emplace_back(v, 0);
		e[v].emplace_back(u, 0);
	}
}

超级源点

因为题目并没有规定从哪一点出发，且题目需要求解出所有情况来判断

因此我们需要一个超级源点来连接所有点，方便求出所有情况

for (int i = 1; i <= n; ++i) e[0].emplace_back(i, 0);

AC代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e4 + 5;
int n, m;
vector<vector<pair<int, int>>> e(N);
ll dis[N]; // 记录距离
int cnt[N]; // 记录任意点在队列的次数，以便判断负环
bool vis[N]; // 记录任意点是否在队列中
void spfa(int s) { // SPFA板子
	queue<int> q;
	q.emplace(s);
	fill(dis + 1, dis + n + 1, INT_MAX); //SPFA必要的初始化
	vis[s] = true;
	dis[s] = 0; // 从超级源点0出发
	while (!q.empty()) {
		int u = q.front(); q.pop();
		vis[u] = false;
		for (auto tmp : e[u]) { // 适配C++14的写法
			int v, w;
			tie(v, w) = tmp;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				cnt[v] = cnt[u] + 1; // 累计点v在队列的次数，因为每个点至多n次，所有如果>n就是有负环
				if (cnt[v] > n) {
					cout << "No\n"; // 有负环，输出NO
					exit(0); // exit(0)是退出整个程序
				}
				if (!vis[v]) {
					vis[v] = true;
					q.emplace(v);
				}
			}
		}
	}
}
int main() {
	// 输入输出加速
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; ++i) {
		int op; cin >> op;
		int u, v, w = 0;
		if (op == 1) { // 第一种边：农场a比农场b至少多种植了c个单位的作物
			cin >> u >> v >> w;
			e[u].emplace_back(v, -w);
		} else if (op == 2) { // 第二种边：农场a比农场b至多多种植了c个单位的作物
			cin >> u >> v >> w;
			e[v].emplace_back(u, w);
		} else { // 第三种边：农场a终止的数量和b一样多
			cin >> u >> v;
			e[u].emplace_back(v, 0);
			e[v].emplace_back(u, 0);
		}
	}
	for (int i = 1; i <= n; ++i) e[0].emplace_back(i, 0); // 建立超级源点
	spfa(0);
	cout << "Yes\n"; // 没有负环输出YES
	return 0;
}

推荐订阅源

文章列表