首页 算法

# 图论

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

# 二叉树

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

前序遍历：按 根 左 右 的顺序进行；

中序遍历：按 左 根 右 的顺序进行；

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

# 最短路 & 生成树

# 算法复杂度

  • 多源最短路 Floyd：严格 O(n3)O(n^3)
  • 单源最短路 Dijkstra：
    • 朴素：严格 O(n2)O(n^2)
    • 优先队列优化：均摊 O((e+n)log⁡n)O((e+n) \log n)
  • Bellman-Ford：
    • 最多松弛 n−1n-1 次
    • 严格 O(ne)O(ne)
  • SPFA：
    • 即队列优化 Bellman-Ford
    • 最坏 O(ne)O(ne)，最好 O(1)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]dis[k][i][j] 表示 i 和 j 之间可以通过编号为 1…k1\dots k 的节点的最短路径，显然，dis[0][i][j]dis[0][i][j] 就是原始邻接矩阵数据。
状态转移方程：
dis[k][i][j]=min(dis[k−1][i][j],dis[k−1][i][k]+dis[k−1][k][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∈[1,n−1])x( x \in [1,n-1]) 次松弛，这样就能产生 n2n^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] 旅行
  
 更新于