洛谷 P2294 [HNOI2005]狡猾的商人

洛谷 P2294 [HNOI2005]狡猾的商人

題目：

• 有圖·。轉鏈接

題解：

• 差分約束。
• 雖然題目中沒有出現不等式，但還是屬于差分約束的范疇之內的。
• 一開始我就按照它的要求u到v加權值w的邊。但發現不行。于是我就又加了一條v到u權值為-w的邊，然后就行了。反思后發現差分約束的題沒弄出來往往是還有約束條件沒有找全。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define N 100005
using namespace std;struct E {int next, to, dis;} e[N];
int T, n, m, num, flag;
int h[N], dis[N], cnt[N];
bool vis[N];void add(int u, int v, int w)
{e[++num].next = h[u];e[num].to = v;e[num].dis = w;h[u] = num;
}int read()
{int x = 0, f = 1; char c = getchar();while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}return x *= f;
}bool spfa(int s)
{queue<int> que;memset(dis, -0x3f, sizeof(dis));dis[s] = 0, vis[s] = 1, que.push(s);while(!que.empty()){int now = que.front();que.pop();  vis[now] = 0;cnt[now]++; if(cnt[now] == n) return 0;for(int i = h[now]; i != 0; i = e[i].next)if(dis[now] + e[i].dis > dis[e[i].to]){dis[e[i].to] = dis[now] + e[i].dis;if(!vis[e[i].to])vis[e[i].to] = 1, que.push(e[i].to);}}return 1;
}int main()
{cin >> T;while(T--){flag = num = 0;memset(h, 0, sizeof(h));memset(cnt, 0, sizeof(cnt));memset(vis, 0, sizeof(vis));n = read(), m = read();for(int i = 1; i <= m; i++){int u = read(), v = read(), w = read();add(u - 1, v, w), add(v, u - 1, -w);}for(int i = 0; i <= n; i++) add(n + 1, i, 0);if(!spfa(n + 1)) printf("false\n");else printf("true\n");}return 0;
}