题目大意
一共 NN 个点， MM 条边。
有 33 种类型的边：
单向边：从点 ii 到点 jj 至少有 cc，也就是 ai−aj≥c
单向边：从点 ii 到点 jj 至多有 cc，ai−aj≤c
双向边：从点 ii 到点 jj一样多，ai=aj
将这 33 种边转换一下可以得到：
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 种边
cc 代表从某一点至某一点的边所需的花费。
对于第一种，从点 ii 到点 jj 至少有 cc：
观察式子 aj≤ai−c 可得出 从点 ii到点 jj 花费为 −c-c
对于第二种，从点 ii 到点 jj 至多有 cc：
观察式子 ai≤aj+c 可得出 从点 jj到点 ii 花费为 cc
对于第三种，从点 ii 到 jj 数量一样，即 cc 为 00：
观察式子 ai=aj+0 与 aj=ai+0 可得出 从点 i/ji/j到点 i/ji/j 花费为 00，是一条双向边
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;
}