图论 - 洛谷保存站

## 最小生成树

kruscarl 算法：先按照权值排序，能连就连。使用并查集维护。

prim 算法：维护一个点集，每次从中向外扩展最小的一条边。

### 例题1 棋盘的守卫者
>一个城市的道路成了像棋盘那样的网状，东西向的路有 N 条，并从北向南从 1 标记到 N，南北向的路有 M 条，并由西向东从 1 标记到 M，每一个交叉点代表一个路口。
>
>为了维护城市治安，需要在一些路口设置岗哨。在每一条东西向的路上，都必须设置且仅设置一个东西方向的岗哨，维护这条路的治安。同样地，在每一条南北向的路上，也必须设置且仅设置一个南北方向的岗哨，来维护这条路的治安。
>
>一个路口最多只能设置一个岗哨。一个岗哨只能维护一条路的治安。在一个路口设置岗哨需要支付一定的费用。在不同的路口，设置岗哨的费用可能是不同的。
>
>问：要想使每条路的治安都得到维护，最少需要支付多少费用？

做法：首先我们需要行列建模，把 $n$ 个点放在左边，$m$ 个点放在右边，左边向右边两两连边，边权就是原网格图的对应点权。方向表示它管理横的还是竖的。然后每个点最多只能有一条入边（因为只能被一个掌管）。所以就变成了求$n+m$ 个点的基环树森林。

具体地，我们在并查集中额外维护一个size表示连通块中环的个数。环的个数不能超过一个。

::::info[code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0;
	char e=getchar();
	while(e<'0'||e>'9') {
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x;
}
const int N=100005;
int n,m;
int fa[N<<1];
bool siz[N<<1];
int Find(int x) {
	if(x==fa[x])return x;
	return fa[x]=Find(fa[x]);
}
struct node {
	int x,y,z;
} a[N];
int tot;
bool cmp(node A,node B){
	return A.z<B.z;
}
signed main() {
//	freopen("ex.in","r",stdin);
//	freopen(".out","w",stdout);
	R(n),R(m);
	for(int i=1; i<=n; ++i) {
		for(int j=1; j<=m; ++j) {
			int R(c);
			a[++tot]= {i,j+n,c};
		}
	}
	sort(a+1,a+1+tot,cmp);
	int ans=0;
	for(int i=1;i<=n+m;++i){
		fa[i]=i;
	}
	for(int i=1; i<=tot; ++i) {
		int x=a[i].x,y=a[i].y,z=a[i].z;
		int fx=Find(x),fy=Find(y);
		if(fx!=fy) {
			if(siz[fx]+siz[fy]<=1) {
				ans+=z;
				siz[fx]+=siz[fy];
				fa[fy]=fx;
			}
		} else if(siz[fx]+siz[fy]==0) {
			siz[fx]=1;
			ans+=z;
		}
	}
	cout<<ans<<"\n";
	return 0;
}
```
::::
## Floyd

Floyd 是最简单的最短路算法，但是有一些需要注意的地方。

在最外层循环到 $k$ 之前，$dp[i][j]$ 存的是从 $i$ 到 $j$ 只经过编号小于 $k$ 的点的最短路。

### 例题1 [P6175 无向图的最小环问题](https://www.luogu.com.cn/problem/P6175)

题意：找出无向图的最小环。

做法：根据 Floyd 的性质，我们在循环到 $k$ 之前，更新一次 $ans$。具体地，枚举 $i<j$，$dp[i][j]$ 就是不经过 $k$ 的最短路。答案就是 $dp[i][j]+a[i][k]+a[j][k]$。

### 例题2 [P10927 Sightseeing trip](https://www.luogu.com.cn/problem/P10927)

题意：上一题的加强版，输出方案。

做法：设计 $pos[i][j]$ 表示用来更新 $i$ 到 $j$ 最短路的 $k$。每一次更新 $dp$ 之前，先更新答案。跟刚才差不多，如果 $ans$ 需要被更新，就更新路径。使用递归更新即可。

递归结束条件：$pos[i][j]=0$。因为根据我们的定义，如果 $i$ 到 $j$ 的边就是 $i,j$ 间最短路，则不需要额外的 $k$。

::::info[code]
$ans$ 为最小环长度。时间复杂度 $\Theta(n^4)$。
```cpp
#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=105,INF=0xccfccfccfccfccf;
int n,m,ans=INF;
int dp[N][N],a[N][N],pos[N][N];
vector<int>path;
void get_path(int x,int y){
	if(!pos[x][y])return ;
	get_path(x,pos[x][y]);
	path.push_back(pos[x][y]);
	get_path(pos[x][y],y);
}
signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	R(n),R(m);
	memset(dp,0x1f,sizeof dp);
	memset(a,0x1f,sizeof a);
	for(int i=1; i<=n; ++i)dp[i][i]=a[i][i]=0;
	for(int i=1; i<=m; ++i) {
		int R(u),R(v),R(w);
		dp[u][v]=min(dp[u][v],w);
		a[u][v]=min(a[u][v],w);
		dp[v][u]=min(dp[v][u],w);
		a[v][u]=min(a[v][u],w);
	}
	for(int k=1; k<=n; ++k) {
		for(int i=1; i<k; i++) {
			for(int j=i+1; j<k; j++) {
				if(ans>dp[i][j]+a[i][k]+a[k][j]) {
					ans=dp[i][j]+a[i][k]+a[k][j];
					path.clear();
					path.push_back(i);
					get_path(i,j);
					path.push_back(j);
					path.push_back(k);
				}
			}
		}
		for(int i=1; i<=n; ++i) {
			for(int j=1; j<=n; ++j) {
				if(dp[i][j]>dp[i][k]+dp[k][j]) {
					dp[i][j]=dp[i][k]+dp[k][j];
					pos[i][j]=k;
				}
			}
		}
	}

if(ans<INF){
		for(int i=0;i<path.size();++i){
			cout<<path[i];
			if(i!=path.size()-1)cout<<" ";
		}
	}
	else{
		cout<<"No solution.";
	}
	return 0;
}
```
::::

## 基环树
基环树是只有一个环的树，解决基环树问题的关键是找环，然后转化为树上问题。

我个人认为基环树题目思路简单，但比较难调。

### 例题1 [P4381 [IOI 2008] Island](https://www.luogu.com.cn/problem/P4381)

题意：给一个基环森林，求直径之和。

思路：对于每个连通块，答案要么为某颗子树的直径，要么经过环。前者直接求，后者断环成链单调队列优化 DP 即可。

::::info[code]
```cpp
#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=2000005;
int head[N],ver[N],val[N],nxt[N],idx=-1;
void add(int x,int y,int z){
	++idx;
	ver[idx]=y,val[idx]=z;
	nxt[idx]=head[x],head[x]=idx;
}
int n;
int dfn[N],times,fa[N];
int a[N],sum[N],d[N],m,mx;
int dp[N],ans,q[N],l,r;
bool vis[N];
void get_loop(int u,int v,int w){
	while(v!=u){
		a[++m]=v;
		sum[m+1]=val[fa[v]];
		v=ver[fa[v]^1];
	}
	a[++m]=u;
	for(int i=1;i<=m;++i){
		vis[a[i]]=1;
		a[i+m]=a[i];
		sum[i+m]=sum[i];
	}
	sum[m+1]=w;
	for(int i=1;i<=m*2;++i){
		sum[i]+=sum[i-1];
	}
}
void dfs(int u){
	dfn[u]=++times;
	for(int i=head[u];~i;i=nxt[i]){
		int v=ver[i];
		if(!dfn[v]){
			fa[v]=i;
			dfs(v);
		}else if((i^1)!=fa[u]&&dfn[v]>dfn[u]){
			get_loop(u,v,val[i]);
		}
	}
}
void DP(int u){
	for(int i=head[u];~i;i=nxt[i]){
		int v=ver[i];
		if(vis[v])continue;
		vis[v]=1;
		DP(v);
		mx=max(mx,d[u]+d[v]+val[i]);
		d[u]=max(d[u],d[v]+val[i]);
	}
}
signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	memset(head,-1,sizeof head);
	R(n);
	for(int u=1;u<=n;++u){
		int R(v),R(w);
		add(u,v,w);
		add(v,u,w);
	}
	for(int u=1;u<=n;++u){
		if(!dfn[u]){
			m=mx=0;
			dfs(u);
			for(int i=1;i<=m;++i){
				DP(a[i]);
			}
			l=1,r=0;
			for(int i=1;i<=2*m;++i){
				while(l<=r&&i-q[l]>=m)++l;
				if(l<=r)mx=max(mx,d[a[i]]+d[a[q[l]]]+sum[i]-sum[q[l]]);
				while(l<=r&&d[a[i]]-sum[i]>=d[a[q[r]]]-sum[q[r]])--r;
				q[++r]=i;
			}
			ans+=mx;
		}
	}
	cout<<ans;
	return 0;
}
/*
6
2 1
1 1
4 1
5 1
3 1
4 100

103
*/
```
::::

### 例题2 [P10933 创世纪](https://www.luogu.com.cn/problem/P10933)

题意：给一个基环树，$A[i]$ 向 $i$ 有一条边。选取其中的一些元素，满足如果选了某个点，不能同时选取他的所有出边的点。求最多选点数量。

思路：建基环树，断掉环上的某条边，然后就变成树了，进行树形 DP。然后得到的答案和真正答案的区别就是没有考虑断掉的边。现在考虑这条边的贡献，再DP 即可。设计 $dp[u][0/1]$ 表示子树 $u$ 的最大值。递推是显然的。

$$
dp[u][0]=\sum_{v=son(u)}\max(dp[v][0],dp[v][1])\\

dp[u][1]=1+\sum_{v=son(u)}\max(dp[v][0],dp[v][1])+\max_{v=son(u)}(dp[v][0]-\max(dp[v][0],dp[v][1]))
$$

解释：不选 $u$ 时，$u$ 的儿子随便选不选都行，故取max。选 $u$ 时，$u$ 的儿子有一个不能选，所以就枚举不选的那个，加入不选 $v$，就减去 $\max(dp[v][0],dp[v][1]))$，再加上$dp[v][0]$。

我们找到一个环上的点为 $root$，然后把 $(a[root],root)$ 这条边记录下来，DP时不走这条边。然后第一次直接DP。第二次为了强制利用这条边，我们不选 $root$，这样 $A[root]$ 就可以随便选儿子了。第一次DP用 $max(dp[root][0],dp[root][1])$ 更新答案，第二次只用 $dp[root][0]$ 更新答案（因为$root$ 用来贡献$A[root]$，不能选）。

::::info[code]
注意：我们通常为了方便，会双向建边，此时，我们在找环的时候一定要注意环的方向。
```cpp
#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0,y=1;
	char e=getchar();
	while(e<'0'||e>'9') {
		if(e=='-')y=-1;
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x*y;
}
const int N=1000005;
int n,ans,tot_ans;
int dfn[N],times,fa[N],root,faroot,del,dp[N][2];
int head[N],ver[N<<1],nxt[N<<1],idx=-1;
int a[N];
void add(int x,int y) {
	++idx;
	ver[idx]=y,nxt[idx]=head[x],head[x]=idx;
}
void dfs(int u) {
	dfn[u]=++times;
	for(int i=head[u]; ~i; i=nxt[i]) {
		int v=ver[i];
		if(!dfn[v]) {
			fa[v]=i;
			dfs(v);
		} else if((i^1)!=fa[u]&&dfn[v]>=dfn[u]) {
			if(a[u]==v)root=u;//v->u
			else root=v;
			faroot=a[root];
			del=i;
		}
	}
}
void DP(int u,int f,int op) {
	dp[u][1]=0;
	dp[u][0]=0; 
	int sum=0;
	for(int i=head[u]; ~i; i=nxt[i]) {
		int v=ver[i];
		if(v==f||i==del||(i^1)==del)continue;
		DP(v,u,op);
		sum+=max(dp[v][0],dp[v][1]);
	}
	dp[u][0]=sum;
	if(op&&u==faroot)dp[u][1]=sum+1;
	else {
		for(int i=head[u]; ~i; i=nxt[i]) {
			int v=ver[i];
			if(v==f||i==del||(i^1)==del)continue;
			dp[u][1]=max(dp[u][1],1+sum-max(dp[v][0],dp[v][1])+dp[v][0]);
		}
	}
	if(u==root) {
		if(!op)ans=max(dp[u][0],dp[u][1]);
		else ans=max(ans,dp[u][0]);
	}
}
signed main() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	memset(head,-1,sizeof head);
	memset(fa,-1,sizeof fa);
	
	R(n);
	for(int i=1; i<=n; ++i) {
		R(a[i]);
		add(i,a[i]),add(a[i],i);
	}
	for(int u=1; u<=n; ++u) {
		if(!dfn[u]) {
			dfs(u);
//			cout<<root<<" "<<faroot<<"\n";
			ans=0;
			DP(root,-1,0);
//			cout<<ans<<"\n";
			DP(root,-1,1);
//			cout<<ans<<"\n";
			tot_ans+=ans;
		}
	}
	cout<<tot_ans<<"\n";
	return 0;
}
```
::::

### 例题3 [P3533 [POI 2012] RAN-Rendezvous](https://www.luogu.com.cn/problem/P3533)

正在渲染内容...