图论

0001-01-01
5分钟阅读时长

图论

图论算法一般都是揉在一起的,很难单独把算法拆开讲,所以直接上题目吧。分类是大致分的,其实有很多是交叉的。

二叉树

二叉树的遍历有三种,分别为前序遍历,中序遍历和后序遍历,并且给定其中的两种遍历能够求出另一种遍历 (必须已知中序遍历)。

前序遍历:按 根 左 右 的顺序进行;

中序遍历:按 左 根 右 的顺序进行;

后序遍历:按 左 右 根 的顺序进行。

最短路 & 生成树

算法复杂度

  • 多源最短路Floyd:严格 $O(n^3)$
  • 单源最短路Dijkstra:
    • 朴素:严格 $O(n^2)$
    • 优先队列优化:均摊 $O((e+n) \log n)$
  • Bellman-Ford:
    • 最多松弛 $n-1$ 次
    • 严格 $O(ne)$
  • SPFA:
    • 即队列优化Bellman-Ford
    • 最坏 $O(ne)$,最好 $O(1)$

板子

咕咕咕

如何卡掉 SPFA

https://www.zhihu.com/question/292283275/answer/484871888

P1967 货车运输

最大生成树,然后跑LCA

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e4+10, M = 1e5+10, INF = 0x3f3f3f3f;

struct node {
	int id, u, v, w, next;
} e[M], e1[M];
int h[N], tot = 0, tot1 = 0, n, m;

int fa[N][15], dep[N], dis[N][15];
int vis[N];
bool edg[M];

void add(int u, int v, int w) {
	e1[tot1] = e[tot] = {tot, u, v, w, h[u]}; h[u] = tot++; tot1++;
	e[tot] = {tot, v, u, w, h[v]}; h[v] = tot++;
}

int bc[N];
int root(int u) {
	return bc[u] == u ? u : bc[u] = root(bc[u]);
}

bool cmp(node a, node b) {
	return a.w > b.w;
}
void dfs(int u, int f, int vi) {
	vis[u] = vi;
	for(int i = h[u]; i != -1; i = e[i].next) {
		int v = e[i].v;
		if(v == f) continue;
		if(edg[i] or edg[i^1]) {
			dep[v] = dep[u] + 1;
			fa[v][0] = u;
			dis[v][0] = e[i].w;
			dfs(v, u, vi);
		}
	}
}

void lca(int x, int y) {
	if(dep[x] < dep[y]) swap(x, y);
	int ans = INF;
	int t = dep[x] - dep[y];
	for(int i=14; i>=0; --i) {
		if(t >= (1<<i)) {
			ans = min(ans, dis[x][i]);
			x = fa[x][i];
			t -= (1<<i);
		}
	}
	if(x == y) {
		printf("%d\n", ans);
		return;
	}
	for(int i=14; i>=0; --i) {
		if(fa[x][i] != fa[y][i]) {
			ans = min(ans, dis[x][i]);
			ans = min(ans, dis[y][i]);
			x = fa[x][i]; y = fa[y][i];
		}
	}
	//printf("lca:%d\n", fa[x][0]);
	printf("%d\n", min(ans, min(dis[x][0], dis[y][0])));
}
int main() {
    
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for(int i=1; i<=m; ++i) {
		int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    
    sort(e1, e1+tot1, cmp);
    for(int i=1; i<=n; ++i) bc[i] = i;
    for(int i=0; i<tot1; ++i) {
    	int u = e1[i].u, v = e1[i].v;
    	int u1 = root(u), v1 = root(v);
    	if(u1 != v1) {
    		edg[e1[i].id] = true;
    		bc[v1] = u1;
		}
	}
	
	for(int i=1; i<=n; ++i) {
		if(bc[i] == i) {
			dfs(i, 0, i);
			for(int j=0; j<=14; ++j) {
				fa[i][j] = i;
				dis[i][j] = INF;
			}
		}
	}
	
	for(int i=1; i<=14; ++i) {
		for(int j=1; j<=n; ++j) {
			fa[j][i] = fa[fa[j][i-1]][i-1];
			dis[j][i] = min(dis[j][i-1], dis[fa[j][i-1]][i-1]);
		}
	}
	
	int query; scanf("%d", &query);
	for(int i=1; i<=query; ++i) { 
		int x, y; scanf("%d%d", &x, &y);
		if(vis[x] != vis[y]) { printf("-1\n"); continue; }
		lca(x, y);
	}
	
    return 0;
} 

P1073 最优贸易

分层图,最短路

#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <iostream>
#include <queue>
#include <map>
using namespace std;

const int N = 330000, M = 1650000;
struct node {
	int u, v, w, next;
	node() {}
	node(int _u, int _v, int _w, int _next): u(_u), v(_v), w(_w), next(_next) {}
} e[M << 1];
int h[N], tot = 0;

inline void add(int u, int v, int w = 0) {
	e[tot] = node(u, v, w, h[u]);
	h[u] = tot++;
}

int n, m, w[N]; bool vis[N]; int dis[N];
int main() {
	
	#ifdef DEBUG
	freopen("p1073_1.in", "r", stdin);
	#endif

	scanf("%d%d", &n, &m);
	for(int i=1; i<=n; ++i) {
		scanf("%d", &w[i]);
	}
	memset(h, -1, sizeof h);
	for(int i=1, x, y, z; i<=m; ++i) {
		scanf("%d%d%d", &x, &y, &z);
		if(z == 1) add(x, y), add(x+n, y+n), add(x+2*n, y+2*n);
		else {
			add(x, y), add(x+n, y+n), add(x+2*n, y+2*n);
			swap(x, y);
			add(x, y), add(x+n, y+n), add(x+2*n, y+2*n);
		}
	}
	
	for(int i=1; i<=n; ++i) {
		add(i+n, i, w[i]);
		add(i, i+2*n, -w[i]);
	}
	
	queue<int> q;
	
	memset(dis, 0x3f, sizeof dis);
	q.push(n+1); vis[n+1] = true; dis[n+1] = 0;
	while(!q.empty()) {
		int u = q.front();
		q.pop(); vis[u] = false;
		for(int i=h[u]; i!=-1; i=e[i].next) {
			int v=e[i].v;
			if(dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				if(!vis[v]) {
					q.push(v);
					vis[v] = true;
				}
			}
		} 
	}
	
	printf("%d\n", -dis[n*3]);
	
	return 0;
}

P1119 灾后重建

很重要的题目,考察了 Floyd的本质。

Floyd

用 $dis[k][i][j]$ 表示 i 和 j 之间可以通过编号为 $1\dots k$ 的节点的最短路径,显然,$dis[0][i][j]$ 就是原始邻接矩阵数据。

状态转移方程:

$$ dis[k][i][j]=min(dis[k-1][i][j],dis[k-1][i][k]+dis[k-1][k][j]) $$

Floyd 的本质其实就是DP,只不过我们通常做题时利用了数据只会使用一次性的原理,把 dis 变成滚动数组,减少了一维,节省空间。

更多请见 https://www.cnblogs.com/fangwencai/p/4784914.html

//提前将邻接矩阵存在 dis 数组里,其他不连通的地方初始化成无穷大
for(int k=1; k<=n; ++k) //枚举中间点
    for(int i=1; i<=n; ++i) //枚举起点
        if(i != k) //节省时间,如果一样就不往下走
            for(int j=1; j<=n; ++j) //枚举终点
                if(i != j and j != k) //继续判断,如果有一样的就不往下走
                    dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); //状态转移方程,也就是所谓的松弛操作

只要我们能够利用 DP 特性,就能解决许多问题

再回来看这道题,文中说每个村子是不同时间修好的,而每个节点都按顺序给出,这不就是恰好相当于 Floyd的中间点吗?我们可以把 k轮 DP分开做,每输入一个点,就用这个点当中转站把最短距离更新一遍,也就是跑一遍 DP。

Code:

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 220;

int t[N];

struct query {
	int id, x, y, t;
} a[55000];

int res[55000], n, m, dp[N][N];
int main() {
	
	//freopen("P1119_2.in", "r", stdin); 
	
	scanf("%d%d", &n, &m);
	
	for(int i=1; i<=n; ++i) {
		scanf("%d", t+i);
	}
	t[n+1] = 0x3f3f3f3f;
	
	memset(dp, 0x3f, sizeof dp);
	
	for(int i=1; i<=n; ++i) dp[i][i] = 0;
	for(int i=1; i<=m; ++i) { int u, v, w;
		scanf("%d%d%d", &u, &v, &w); ++u, ++v;
		dp[u][v] = dp[v][u] = w;
	}
	int q;
	scanf("%d", &q);
	for(int i=1; i<=q; ++i) {
		scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].t);
		a[i].id = i; ++a[i].x, ++a[i].y; 
	}
	
	int cnt = 1;
	for(; a[cnt].t < t[1]; ++cnt) {
		res[a[cnt].id] = -1; 
	}
	
	for(int T=1; T<=n; ++T) {
		
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j) {
				dp[i][j] = min(dp[i][j], dp[i][T] + dp[T][j]);
			}
		}
			
		while(1) {
			if(cnt > q) break;
			if(a[cnt].t >= t[T] and a[cnt].t < t[T+1]); else break;
			if(a[cnt].x > T or a[cnt].y > T or dp[a[cnt].x][a[cnt].y] == 0x3f3f3f3f) {
				res[a[cnt].id] = -1;
			} else {
				res[a[cnt].id] = dp[a[cnt].x][a[cnt].y];
			}
			++cnt;
		}
	}
	
	for(int i=1; i<=q; ++i) printf("%d\n", res[i]);
	return 0;
}

判负环

转自 @SingerCoder,%lgh

注意一定要判入队次数而不是松弛次数。

hack原理很简单:如果存在重边导致了多次松弛,那么对松弛次数的判断就会产生影响。解决方式就是判入队次数,虽然略慢,但是更稳。

Update[2020.7.26]:在写差分约束的时候想用spfa判无解,然后经过一系列的思考就有了下面这组新的hack数据:

input:
1
4 6
1 2 -3
1 3 -2
1 4 -1
2 3 -6
2 4 -5
3 4 -4
output:
NO

注意这组hack只对用链式前向星(而非vector)存边且判的是松弛次数(而非入队次数)的有效,而且该数据无重边无自环,比discuss里面的那个数据更有说服力。

首先hack原理就是对n号节点进行n-1轮松弛,每轮都有 $x( x \in [1,n-1])$ 次松弛,这样就能产生 $n^2$ 级别的松弛次数。

但是判入队次数就hack不掉了,每轮的第一次松弛会让n节点入队,但n节点只有在下一轮才会出队;因此本轮的其余所有松弛全部无法导致入队。

P3385 [模板]负环

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
using namespace std;

const int N = 2e3 + 10, M = 6e3 + 10;
struct node {
	int u, v, w, next;
} e[M];
int h[N], tot = 0;
int T, n, m;
inline void add(int u, int v, int w) {
	e[++tot] = {u, v, w, h[u]}; h[u] = tot;
} 

int dis[N], vis[N];
bool inq[N];

inline void spfa() {
	
	queue<int> q;
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	memset(inq, false, sizeof inq);
	
	dis[1] = 0; q.push(1); inq[1] = true; ++vis[1];
	while(!q.empty()) {
		
		int u = q.front(); q.pop(); inq[u] = false;//printf("%d\n", u);
		for(int i = h[u]; i ; i = e[i].next) {
			int v = e[i].v;
			if(dis[v] > dis[u] + e[i].w) {
				dis[v] = dis[u] + e[i].w;
				if(!inq[v]) {
					inq[v] = true;
					++vis[v];
					if(vis[v] > n-1) {
						printf("YES\n");
						return;
					}
					q.push(v);
				}
			}
		}
	}
	printf("NO\n");
}
int main() {
	
	//freopen("P3385_2.in", "r", stdin);
	
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		memset(h, 0, sizeof h); tot = 0;
		for(int i=1; i<=m; ++i) {
			int u, v, w; scanf("%d%d%d", &u, &v, &w);
			if(w >= 0) {
				add(u, v, w);
				add(v, u, w);
			} else add(u, v, w);
			//printf("%d ", i);
		}
		spfa();
	}
	return 0;
}

基环树

n 个点 n 条边 只有一个环 枚举断边

P5022 [NOIp2018TG]旅行

上一页 单调队列
下一页 图论:LCA