2025.8.6 图论（1）Solution-EW帮帮网

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;
        //更新dis
        for(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]);
		}
		else
			if(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$ ）的距离减去两倍根节点到 $L C A (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 可不可以判断负环呢？如果可以，怎么判断？如果不行，又为什么？

欧拉道路

学习资料。

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

2025.8.6 图论（1）Solution