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 可不可以判斷負環呢？如果可以，怎么判斷？如果不行，又為什么？

歐拉道路

學習資料。

不過有點冷門了，考試一般不會考……