關于最短路、負環、差分約束系統的一點筆記

最短路

“可以”沒有環，最多\(|V|-1\)條邊

有負環則不存在最短路

會形成最短路徑樹

算法

1. Dijkstra 貪心，當\(d_u\)是最小時要滿足之后\(d_u\)不會更小，不能處理負權邊
2. Bellman-Ford 迭代n-1輪，用邊松弛
3. spfa 隊列優化的Bellman-Ford

最短路的線性規劃形式

最大化 \(d_i\)

滿足

1. 三角不等式 $d_v \le d_u + w(u,v),\ $
2. \(d_s=0\)

說明：上述約束對應了無窮組解。最短路求的是滿足約束的最大值。因為三角不等式要求取等號時w(u,v)是最短路上的邊。

應用

差分約束系統

非DAG上DP

一般使用spfa或者縮點后dp

應為dijkstra有貪心策略的限制

負環

將所有點入隊，且\(d_i=0\)

負環只看不等約束，不看初始值

算法

1. Bellman-Ford 常數小
2. spfa 判斷 1. 入隊次數>=n 2.最短路長度>=n
3. spfa-dfs 沒多大意思，輕松被卡

應用

01分數規劃

代碼

見最后

差分約束系統

舊

和最短路的線性規劃形式類似的一類線性規劃問題

也是需要初值的，對應d[s]=0

最短路

最大化

有負環則無解

圖不連通 無關 任意解

最長路

最小化

有正環則無解

圖不連通 無關 任意解

當然也可以轉化成最短路

附錄：

判負環的代碼

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2005, M = 3005;

inline 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;
}

int n, m;
struct edge {int v, ne, w, u;} e[M<<1];
int cnt, h[N];
inline void ins(int u, int v, int w) {
	e[++cnt] = (edge) {v, h[u], w, u}; h[u] = cnt;
}

int d[N], cou[N];
bool bellman_ford() {
	for(int i=1; i<=n; i++) d[i] = cou[i] = 0;
	for(int i=1; i<=n; i++) {
		for(int i=1; i<=cnt; i++) {
			int u = e[i].u, v = e[i].v; //printf("hi %d %d  %d %d\n", u, v, d[u], d[v]);
			if(d[v] > d[u] + e[i].w) {
				d[v] = d[u] + e[i].w;
				cou[v] = cou[u] + 1;
				if(cou[v] >= n) return false;
				if(i == n) return false;
			}
		}
	}
	return true;
}
int main() {
	freopen("in", "r", stdin);
	int T = read();
	while(T--) {
		cnt = 0; memset(h, 0, sizeof(h));

		n = read(); m = read();
		for(int i=1; i<=m; i++) {
			int u = read(), v = read(), w = read();
			if(w < 0) ins(u, v, w);
			else ins(u, v, w), ins(v, u, w);
		}
		puts(bellman_ford() ? "N0" : "YE5");
	}
}

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2005, M = 3005;

inline 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;
}

int n, m;
struct edge {int v, ne, w;} e[M<<1];
int cnt, h[N];
inline void ins(int u, int v, int w) {
	e[++cnt] = (edge) {v, h[u], w}; h[u] = cnt;
}
int d[N], cou[N], inq[N], cinq[N];
int q[N], head, tail;
inline void lop(int &x) {if(x==N) x=1;}
bool spfa() {
	head = tail = 1;
	for(int i=1; i<=n; i++) d[i] = cou[i] = 0, inq[i] = cinq[i] = 1, q[tail++] = i;
	while(head != tail) {
		int u = q[head++]; lop(head); inq[u] = 0;
		for(int i=h[u]; i; i=e[i].ne) {
			int v = e[i].v;
			if(d[v] > d[u] + e[i].w) {
				d[v] = d[u] + e[i].w;
				cou[v] = cou[u] + 1;
				if(cou[v] >= n) return false;
				if(!inq[v]) {
					q[tail++] = v; lop(tail); inq[v] = 1; 
					if(++cinq[v] >= n) return false; 
				}
			}
		}
	}
	return true;
}

int main() {
	freopen("in", "r", stdin);
	int T = read();
	while(T--) {
		cnt = 0; memset(h, 0, sizeof(h));

		n = read(); m = read();
		for(int i=1; i<=m; i++) {
			int u = read(), v = read(), w = read();
			if(w < 0) ins(u, v, w);
			else ins(u, v, w), ins(v, u, w);
		}
		puts(spfa() ? "N0" : "YE5");
	}
}