前言

本文是笔者所写 图论总结 的练习题部分，分开为一篇文章。

本文主要有关图论题目和相关知识点和 thick

part 1 图的存储与遍历

P2921 Trick or Treat on the Farm G

基环树 + dfs

题意：

有一张图，奶牛从图中每一个点出发，当奶牛重复经过一个点时停止移动，求每头奶牛所经过的点的数量

solution

容易得出，所给的图是一个外向基环森林，每头奶牛所经过的点的数量即当前奶牛所在的基环树上环的点数加上奶牛所在的点到环上的距离

所以可以枚举每个连通块，在连通块中：

  1. 求当前基环树环的点数
  2. 将环缩为一个点
  3. 求点到所有其他点的距离，统计答案

具体地，我们可以将外向基环树转化为内向基环树，从而求环上一点，进一步求得环上所有点，代码如下

int find(int x){
	if(vis1[x]) return x;
	vis1[x] = 1;
	return find(fa[x]);
}

int find2(int x){
	if(vis[x]) return x;
	vis[x] = 1 , cnt ++ , q.push(x);
	return find2(fa[x]); 
}

find 函数求环上一个点，find2 函数求环上所有点

随后统计环上点连的环外的点，用一个虚点连这些边，此时得到了一颗以虚点为根的树，在树上求其他点到根的距离即可

part 2 最短路

P1144 最短路计数

bfs 最短路 + dp 计数

solution

考虑在 bfs 中 dp，用 bfs 求边权为 11 的图的最短路

设 dpxdp_x 为从 11 ~ xx 的最短路数量， disxdis_x 为从 11 ~ xx 的最短路长度

显然，只有在第一次遍历到节点 xx 或当前是最短路时(即 disx=disu+1dis_x = dis_u + 1)才能更新 dpxdp_x，状态转移方程为：

dpx=dpx+dpudp_x = dp_x + dp_u

注意每个点只能入队一次，但可以被遍历多次，所以当第一次遍历到节点 xx 时入队

关键代码如下：

void bfs(int s){
	queue<int> q;
	q.push(s);
	
	while(!q.empty()){
		int u = q.front();
		q.pop();
		for(int i = 0 ; i < g[u].size() ; i ++){
			int v = g[u][i];
			
			if(dis[v] == 0 || dis[v] == dis[u] + 1){
				if(!dis[v]){
					dis[v] = dis[u] + 1;
					q.push(v);
				}
				dp[v] = (dp[v] + dp[u]) % mod;
			}
		}
	}
}

P1522 [USACO2.4] 牛的旅行 Cow Tours

floyd 算法 + 并查集

solution

这道题比较复杂，可以先用并查集求出所有的连通块，再用 floyd 求出所有点对之间的最短路径

然后观察发现数据范围比较小，因此可以枚举所有点对，连边后统计答案（最小直径）。显然，答案为

ans=max⁡(mxi+mxj+w,dx,dy)ans = \max(mx_i + mx_j + w , d_x , d_y)

其中 mximx_i 为 ii 到所有点最短路径的最大值 , x,yx,y 分别为点 i,ji,j 所在连通块，dxd_x 为连通块直径，ww 为 (i,j)(i,j) 的边权

所以我们可以预处理出每个点的 mx 值和所有连通块的直径即可

P4568 [JLOI2011] 飞行路线

分层图 + 最短路

solution

如果没有免费次数的话，这题就是个最短路板子。加上免费次数的话要将点拆为 k+1k + 1 种状态，分别对应在这个点用了 00 次次数，用 11 次...用 kk 次。

此时的图就变为了分层图，用 dijkstra 算法，考虑设 disx,kdis_{x,k} 为到点 xx 用了 kk 次次数的最短路长度，有如下转移：

$$\begin{align} &dis_{x,k} = \min(dis_{y,k - 1} , dis_{x,k}) \\ &dis_{x,k} = \min(dis_{y,k} + w(y , x) , dis_{x,k}) \end{align}$$

注意在分层图上 visvis 数组要开二维，此外在队列中的点也要把状态存进去

关键代码如下：

void dijkstra(){
	priority_queue<node> q;
	q.push({s , 0 , 0});
	
	memset(dis , 0x3f3f3f3f , sizeof dis);
	dis[s][0] = 0;
	
	while(!q.empty()){
		node u = q.top(); q.pop();
		if(vis[u.x][u.f]) continue;
		vis[u.x][u.f] = 1;
		
		for(auto v : g[u.x]){
			if(vis[v.to][u.f]) continue;
			if(dis[v.to][u.f] > u.p + v.w){
				dis[v.to][u.f] = u.p + v.w;
				q.push({v.to , dis[v.to][u.f] , u.f});
			}
			if(vis[v.to][u.f + 1] || u.f + 1 > k) continue;
			if(dis[v.to][u.f + 1] > u.p){
				dis[v.to][u.f + 1] = u.p;
				q.push({v.to , dis[v.to][u.f + 1] , u.f + 1});
			}
		}
	}
	int ans = 0x3f3f3f3f;
	for(int i = 0 ; i <= k ; i ++){
		ans = min(ans , dis[t][i]);
	}
	cout << ans;
}

P9751 [CSP-J 2023] 旅游巴士

分层图 + 最短路

solution

将点拆为 k+1k + 1 种状态，disx,jdis_{x,j} 表示点 xx 到 11 的时间，满足当前时间mod  k=j\mod k = j ,设当前时间为 pp ,于是我们有如下转移：

$$dis_{x,(p + 1)\mod k} = \min(dis_{x,(p + 1)\mod k} , p + 1)$$

当前时间初始值为 00 , 每到一个点时间更新为此点的 disdis 值

但是此题还有一个限制：经过边的时间 ⩾a\geqslant a，所以当时间 ⩽a\leqslant a 时，出发时要额外加上 k×⌈a−pk⌉k \times \lceil \frac{a - p}{k} \rceil 时间，但是在编码上可以直接将当前时间加 k×⌈a−pk⌉k \times \lceil \frac{a - p}{k} \rceil 表示为原地等待时间，可以证明这对答案不影响

所以时间 ⩽a\leqslant a 的转移为

$$\begin{split} &p' = p + k \times \lceil \frac{a - p}{k} \rceil \\ &dis_{x,(p' + 1)\mod k} = \min(dis_{x,(p' + 1)\mod k} , p' + 1) \end{split}$$

最后的答案即为 disn,0dis_{n , 0}

P5304 [GXOI/GZOI2019] 旅行者

最短路

solution

首先考虑暴力：直接枚举每一个感兴趣的点，求这些点的最短路，随后统计最短路的最小值即可。

然而暴力显然会 T ，考虑优化，注意到可以将所有感兴趣的点分为两个子集 A 和 B，然后用 s 连接 A 中所有的点，然后用 t 连接 B 中所有的点，求 s 和 t 的最短路即求：

min⁡i∈A&j∈B(disi,j)\min_{i \in A \& j \in B}(dis_{i , j})

可见我们只要用一种分类方式，将最短感兴趣的点分到不同的集合中即可，设最短的两个点为 x,yx,y 。因为 x≠yx \neq y 所以 x,yx,y 中必有一二进制位不同，所以可以枚举进制位，按 0/10/1 分类即可

注意有于图是有向图，所以分类后要跑两遍 dijkstra

关键代码如下：

void solve1(vector<int> a , vector<int> b){
	for(auto it : a) g[s].push_back({it , 0});
	for(auto it : b) g[it].push_back({t , 0});
	
	dijkstra();
	ans = min(ans , dis[t]);
	
	g[s].clear();
	for(auto it : b) g[it].pop_back();
}

void solve(){
	cin >> n >> m >> k;
	ans = inf , s = 0 , t = n + 1;
	
	for(int i = 0 ; i < N ; i ++){
		g[i].clear();
	}
	for(int i = 1 ; i <= m ; i ++){
		int x , y , w;
		cin >> x >> y >> w;
		g[x].push_back({y , w});
	}
	for(int i = 1 ; i <= k ; i ++){
		cin >> p[i];
	}
	for(int i = 1 ; i <= 20 ; i ++){
		vector<int> tmp1 , tmp2;
		for(int j = 1 ; j <= k ; j ++){
			if(p[j] & (1 << i)) tmp1.push_back(p[j]);
			else tmp2.push_back(p[j]);
		}
		solve1(tmp1 , tmp2);
		solve1(tmp2 , tmp1);
	}
	cout << ans << '\n';
}

P4001 [ICPC-Beijing 2006] 狼抓兔子

最小割 + 对偶图 + 最短路

solution

这道题显然可以直接建图然后再图上跑最大流板子即可，但是我不会最大流（可能被卡），所以我们用对偶图解决

什么是对偶图？

简单来说，对偶图就是将点嵌再原来图的空格中，对偶图的每个边都对应原图的一条边。

对于本题，可以建一个对偶图，随后建一个超级源点与超级汇点连在图边缘的边所对应的对偶图上的点，此时，在对偶图上跑最短路即为答案

定理 ：在平面图上，最大流 = 最小割 = 对偶图最短路

关键代码如下：

// 建图
	for(int i = 1 ; i <= n ; i ++){
		int id = 2 * (i - 2) * (m - 1);
		
		for(int j = 1 ; j <= m - 1 ; j ++){
			int x;
			cin >> x;
			if(i == 1){
				add_e(2 * j , t , x);
			}
			else if(i == n){
				add_e(s , id + 2 * j - 1 , x);
			}
			else{
				add_e(2 * j - 1 + id , 2 * j - 1 + id + a , x);
				add_e(2 * j - 1 + id + a , 2 * j - 1 + id , x);
			}
		}
	}
	for(int i = 1 ; i <= n - 1 ; i ++){
		int id = 2 * (i - 1) * (m - 1);
		
		for(int j = 1 ; j <= m ; j ++){
			int x;
			cin >> x;
			if(j == 1){
				add_e(s , 2 * (i - 1) * (m - 1) + 1 , x);
			}
			else if(j == m){
				add_e(2 * i * (m - 1) , t , x);
			}
			else{
				add_e(2 * (j - 1) + id , 2 * (j - 1) + id + 1 , x);
				add_e(2 * (j - 1) + id + 1 , 2 * (j - 1) + id , x);
			}
		}
	}
	for(int i = 1 ; i <= n - 1 ; i ++){
		int id = 2 * (i - 1) * (m - 1);
		
		for(int j = 1 ; j <= m - 1 ; j ++){
			int x;
			cin >> x;
			add_e(2 * j - 1 + id , 2 * j + id , x);
			add_e(2 * j + id , 2 * j - 1 + id , x);
		}
	}
	dijkstra();

part 3 最小生成树

P1967 [NOIP 2013 提高组] 货车运输

最小生成树 + lca + dp

solution

题意就是在图上给定 qq 个询问，求 (u,v)(u,v) 的所有路径中边权最小的边中的最大值

直接在图上求十分困难，考虑贪心。显然，有一些边权较小路径我们是不会经过的，所以可以将这些路径去掉。这时即可以在图上求最大生成树，然后在最大生成树处理询问

于是询问就转化为树上问题，求 (u,v)(u,v) 路径上最小边权。(u,v)(u,v) 路径可转化为 (u,lcau,v)(u,lca_{u,v})，(lcau,v,v)(lca_{u,v},v) 两条路径，所以可以在求 lca 时处理

借鉴求 lca 的思路，设 fu,if_{u,i} 为从 uu 到 uu 的 2i2^i 级祖先路径上最小边权。显然 fu,0=w(u,fau)f_{u,0} = w(u , fa_u)，转移如下：

$$f_{u,i} = \min(f_{u , i - 1} , f_{fa_{u , i - 1} , i-1})$$

和 lca 过程中 fa 的转移过程差不多

随后在求 lca 统计最小边权即可。

注意：本题目中所给的图不一定联通，所以要分别对每个连通分量 dfs

关键代码如下：

void kruskal(){
	for(int i = 1 ; i <= n ; i ++) fa[i] = i;
	
	for(int i = 1 ; i <= m ; i ++){
		if(uni(e[i].x , e[i].y)){
			g[e[i].x].push_back(edge{e[i].y , e[i].w});
			g[e[i].y].push_back(edge{e[i].x , e[i].w});
		}
	}
}

void dfs(int x , int f , int k){
	vis[x] = 1;
	for(int i = 0 ; i < g[x].size() ; i ++){
		edge t = g[x][i];
		if(t.x != f){
			dp[t.x][0] = t.w , fath[t.x][0] = x , d[t.x] = d[x] + 1;
			for(int i = 1 ; i <= lg[d[t.x]] ; i ++){
				fath[t.x][i] = fath[fath[t.x][i - 1]][i - 1];
				dp[t.x][i] = min(dp[t.x][i - 1] , dp[fath[t.x][i - 1]][i - 1]);
			}
			dfs(t.x , x , k);
		}
	}
}

int solve(int x , int y){
	if(find(x) != find(y)) return -1;
	if(d[x] < d[y]) swap(x , y);
	int res = 0x3f3f3f3f;
	
	while(d[x] > d[y]){
		res = min(res , dp[x][lg[d[x] - d[y]] - 1]);
		x = fath[x][lg[d[x] - d[y]] - 1];
	}
	if(x == y) return res;
	for(int k = lg[d[x]] - 1 ; k >= 0 ; k --){
		if(fath[x][k] != fath[y][k]){
			res = min(res , min(dp[x][k] , dp[y][k])) , x = fath[x][k] , y = fath[y][k];
		}
	}
	return min(res , min(dp[x][0] , dp[y][0]));
}
  1. Language
  2. 兼容模式
  3. 主题
  3. Worker 0, 23ms
  4. Powered by Hydro v5.0.0-beta.13 Community