2025.8.6 图论（1）Solution

割点

学习资料，在 csdn 或洛谷上看都行。是模板题题解（之一）。

T1：Atserckcn与逃离恐怖老师。

题意简述：从一个图中选定一个点，使得删除这个点后图不连通。求该点编号，无解输出 -1。图不一定联通。

那么本题显然就是割点模板题，在模板题代码中稍微修改即可。

最小生成树

最小生成树一般有两种算法：Kruskal and Prim。

kruskal

基本思想：采取贪心的思想，对边按边权为关键字，从小到大排序。遍历所有边，用并查集维护边连接的两个点。如果两个点之前并不在一个连通块中，那么此边就是最小生成树中的其中一个边。反之跳过。直至选择了 $n-1$ 条边，变成了一棵树。

实例代码：

sort(edge+1,edge+m+1,cmp);//对边进行排序for(int i=1;i<=m;i++)//遍历每条边{if(!Union(edge[i].u,edge[i].v))//检查u,v是否在同一连通块{//是的话，选取这条边。ans+=edge[i].w;cnt++;}if(cnt>=n-1){break;}}

Prim

思想：也是运用贪心的思想，不过不同于 Kruskal 的是，Kruskal 是按照边进行贪心选取，而 Prim 是基于点。

• 一开始先将点 $1$ 加入生成树。

• 维护一个数组，表示每个点到目前最小生成树的距离，执行 $n-1$ 次，每次选取最近的一个点加入生成树，并更新距离。

for(re int i=2;i<=n;++i)dis[i]=inf;for(re int i=head[1];i;i=e[i].next)dis[e[i].v]=min(dis[e[i].v],e[i].w);//更新while(++tot<n)//再次加入n-1个点{int minn=inf;vis[now]=1;for(int i=1;i<=n;++i){if(!vis[i]&&minn>dis[i]){minn=dis[i];now=i;}}ans+=minn;//更新disfor(int i=head[now];i;i=e[i].next){int v=e[i].v;if(dis[v]>e[i].w&&!vis[v])dis[v]=e[i].w;}}return ans;

从TJ区搞过来的，大家可以自行试试。

T2：Atserckcn 与选取隧道

原题：YZOJ P1038 – 隧道

思路：

• 因为道路/隧道需要连接每个岛，并且它们的建设数量要最小，所以不难看出总结果一定是一棵树。
• 岛上的居民喜欢隧道，而不是桥梁，那么就多选隧道。
• 隧道对答案的贡献是 $0$
• 桥梁对答案的贡献是 $1$
• 可以将每条隧道的权值设为 $0$，桥梁的权值设为 $1$，用 Kruskal 或 Prim 实现

实现代码：（kruskal）

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,K=1.2e4+5,M=K;
int n,k,m,fa[N],cnt_e,ans,cnt;
struct E{int from,to,w;
}e[K+M];
bool operator < (const E &x,const E &y)//按照权值小到大排序
{return x.w<y.w;
}
int findfa(int x)//并查集部分
{return fa[x]==x?x:fa[x]=findfa(fa[x]);
}
void Union(int x,int y)
{fa[findfa(x)]=findfa(y);return;
}
void kruskal()
{sort(e+1,e+cnt_e+1);for(int i=1;i<=cnt_e;++i){int u=e[i].from,v=e[i].to,w=e[i].w;if(findfa(u)!=findfa(v)){Union(u,v);++cnt;ans+=w;if(cnt>=n-1)break;}}return;
}
int main(){ios::sync_with_stdio(0);cin>>n>>k>>m;for(int i=1;i<=n;++i)fa[i]=i;for(int i=1;i<=k;++i){++cnt_e;cin>>e[cnt_e].from>>e[cnt_e].to;e[cnt_e].w=0;}for(int i=1;i<=m;++i){++cnt_e;cin>>e[cnt_e].from>>e[cnt_e].to;e[cnt_e].w=1;}kruskal();cout<<ans<<'\n';return 0;
}

缩点

前置知识点：强连通分量。学习资料。

原题：YZOJ P1332 – Love

对于本题，$O(n^2)$ 的枚举肯定超时，考虑优化。

将粉丝视为点，$u$ 崇拜 $v$ 则当为一条连接 $(u,v)$ 的有向边。

• 如果某个连通块里的所有人都互相崇拜，那么这一大块的人目前都是最无脑粉丝
• 考虑运用强连通分量，将上述的所有互相崇拜的联通块视作一个点，在新图上操作。
• 接下来看出度，如果这个点没有出度，说明他们没有崇拜的人，都可能是最佳无脑粉丝
• 但是如果有两个以上这样的连通块，最佳无脑粉丝就一个都不是。

实例代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=1e6+5;
int n,m,ehead[N],cnt_e,dfn[N],low[N],idx,tot,belong[N],deg[N],siz[N],ans,cntans;
stack<int> st;
bool inst[N];
struct E{int to,pre;
}e[M];
void adde(int from,int to)
{e[++cnt_e].to=to;e[cnt_e].pre=ehead[from];ehead[from]=cnt_e;return;
}
void dfs(int u)
{low[u]=dfn[u]=++idx;inst[u]=1;st.push(u);for(int i=ehead[u];i;i=e[i].pre){int v=e[i].to;if(!dfn[v]){dfs(v);low[u]=min(low[u],low[v]);}elseif(inst[v])low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){vector<int> vec;vec.clear();++tot;while(1){int t=st.top();st.pop();vec.push_back(t);inst[t]=0;if(t==u)break;}for(int i=0;i<(int)vec.size();++i)belong[vec[i]]=tot;for(int i=0;i<(int)vec.size();++i){int u=vec[i];for(int j=ehead[u];j;j=e[j].pre){int v=e[j].to;if(belong[v]!=tot)++deg[tot];}}siz[tot]=vec.size();
//		cout<<tot<<":\n";
//		for(int i=0;i<(int)vec.size();++i)
//			cout<<vec[i]<<' ';
//		cout<<'\n';vec.clear();}return;
}
int main(){ios::sync_with_stdio(0);cin>>n>>m;for(int i=1,u,v;i<=m;++i){cin>>u>>v;adde(u,v);}for(int i=1;i<=n;++i)if(!dfn[i])dfs(i);
//	for(int i=1;i<=n;++i)
//		cout<<belong[i]<<' ';
//	cout<<'\n';for(int i=1;i<=tot;++i){if(!deg[i]){ans+=siz[i];++cntans;}}if(cntans>1){cout<<"0\n";return 0;}cout<<ans<<'\n';return 0;
}

LCA

学习资料。

对于本题，由于在一棵树上，两点的距离就是两点 $a,b$ 到根节点（假定为 $1$）的距离减去两倍根节点到 $LCA(a,b)$ 的距离，不懂画个图就懂。

示例代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,q,cnt_e,ehead[N],dis[N],fa[N][25],dep[N];
struct E{int to,w,pre;
}e[N<<1];
void adde(int from,int to,int w)
{e[++cnt_e].to=to;e[cnt_e].w=w;e[cnt_e].pre=ehead[from];ehead[from]=cnt_e;return;
}
void dfs(int u,int u_f)
{fa[u][0]=u_f;for(int i=1;i<=20;++i)fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=ehead[u];i;i=e[i].pre){int v=e[i].to,w=e[i].w;if(v==u_f)continue;dis[v]=dis[u]+w;dep[v]=dep[u]+1;dfs(v,u);}return;
}
int getlca(int x,int y)
{if(dep[x]<dep[y])swap(x,y);//dep[x]>=dep[y]for(int i=20;i>=0;--i)//倍增{if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];}if(x==y)return x;for(int i=20;i>=0;--i){if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}}return fa[x][0];
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>q;for(int i=1,u,v,w;i<n;++i){cin>>u>>v>>w;adde(u,v,w);adde(v,u,w);}dfs(1,1);while(q--){int x,y,lcaxy;cin>>x>>y;lcaxy=getlca(x,y);cout<<dis[x]+dis[y]-2*dis[lcaxy]<<'\n';}return 0;
}

题目讲解完毕，看一些其他算法：

单源最短路——Floyd 算法

本质是个 dp，用 $f_{k,i,j}$ 表示只经过前 $k$ 个点，$i,j$ 之间的最短路径。

每次转移有两种选择：

• 经过第 $k$ 个点，$f_{k,i,j}=f_{k-1,i,k}+f_{k-1,k,j}$。
• 不经过，$f_{k,i,j}=f_{k-1,i,j}$。

注意到 $f_{k,i,j}$ 的转移只跟 $f_{k-1,i,j}$ 有关系，所以可以省去 $k$ 这一维，运用状态的继承性。

核心代码：

for(int k=1;k<=n;++k)for(int i=1;i<=n;++i)for(int j=1;j<=n;++j)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);

问题：

那么 Floyd 可不可以判断负环呢？如果可以，怎么判断？如果不行，又为什么？

欧拉道路

学习资料。

不过有点冷门了，考试一般不会考……