最小生成树
[生成树]
从一个无向连通图中选取一些边使这张图是一颗树。
[最小生成树]
在生成树的基础上使边权和最小。
[Kruskal]
寻找满足条件的边
贪心，从未选取的边中选一条边权最小的边，
选完后不出环即可。
我们需要判断:
1.当前最小边权的边。
2.这条边所连接的两个点的连通性。
用并查集判断即可。
[Prim]
寻找满足条件的点
在没有加入连通块的点中选一个最近的加入连通块，
我们需要判断:
1.哪些点还没有加入连通块
2.这些点与连通块的距离
3.距离最近的点
eg:
1.
accoders【一本通图 最小生成树】最短网络(agrinet)2023
luogu P1546 [USACO3.1] 最短网络 Agri-Net
思路:
最小生成树的板子。
[Kruskal]
code:
#include<bits/stdc++.h>
using namespace std;
int n,a[110][110];
struct node{
int l,r,w;
bool operator <(const node &ret)const{
return w<ret.w;
}
}e[1000010];
int cnt,fa[1000100],ans=0,tot=0;
int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
if(i<j){
e[++cnt]={i,j,a[i][j]};
}
}
}
for(int i=1;i<=n;i++){
fa[i]=i;
}
sort(e+1,e+cnt+1);
for(int i=1;i<=cnt;i++){
int l=e[i].l,r=e[i].r,w=e[i].w;
int fl=find(l),fr=find(r);
if(fl!=fr){
fa[fl]=fr;
tot++;
ans+=w;
}
if(tot==n-1){
break;
}
}
cout<<ans;
return 0;
}
2.
accoders的【一本通图 最小生成树】 局域网
luogu P2820 局域网
思路:
求出最小生成树后用边权总和减去最小生成树的边权和即可。
[Prim]
code:
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
const int N=100010;
struct node{
int to,l;
};
int n,m,ans,tot;
vector<node>mp[N+10];
int vis[N+10],dis[N+10];
void prim(int rt){
priority_queue<P,vector<P>,greater<P> >q;
dis[rt]=0;
q.push(P(dis[rt],rt));
while(!q.empty()){
int l=q.top().second,w=q.top().first;
q.pop();
if(vis[l]){
continue;
}
vis[l]=1;
ans+=w;
for(auto v:mp[l]){
if(dis[v.to]>v.l){
dis[v.to]=v.l;
q.push(P(dis[v.to],v.to));
}
}
}
}
int main(){
cin>>n>>m;
memset(dis,0x3f3f3f3f,sizeof dis);
for(int i=1;i<=m;i++){
int l,r,w;
cin>>l>>r>>w;
mp[l].push_back({r,w});
mp[r].push_back({l,w});
tot+=w;
}
prim(1);
cout<<tot-ans;
return 0;
}
[Kruskal]
#include<bits/stdc++.h>
using namespace std;
int n,k,cnt;
struct node{
int l,r,w;
bool operator <(const node &W)const{
return w<W.w;
}
}mp[110*110];
int fa[110*110];
int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}
int main(){
cin>>n>>k;
int tot=0,ans=0;
for(int i=1;i<=k;i++){
int l,r,w;
cin>>l>>r>>w;
mp[++cnt]={l,r,w};
tot+=w;
}
for(int i=1;i<=n;i++){
fa[i]=i;
}
sort(mp+1,mp+cnt+1);
for(int i=1;i<=cnt;i++){
int l=mp[i].l,r=mp[i].r,w=mp[i].w;
int fl=find(l),fr=find(r);
if(fl!=fr){
fa[fl]=fr;
ans+=w;
}
}
cout<<tot-ans;
return 0;
}
3.
accoders的【一本通图 最小生成树】 繁忙的都市 2025
luogu P2330 [SCOI2005] 繁忙的都市
思路:
最小生成树但是要求有多少个边和边权最大的边。
code:
[Kruskal]
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt,tot,ma=-1;
struct node{
int l,r,w;
bool operator <(const node &W)const{
return w<W.w;
}
}mp[310*310];
int fa[310*310];
int find(int x){
if(x==fa[x]){
return x;
}
return fa[x]=find(fa[x]);
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int l,r,w;
cin>>l>>r>>w;
mp[++cnt]={l,r,w};
}
for(int i=1;i<=n;i++){
fa[i]=i;
}
sort(mp+1,mp+cnt+1);
for(int i=1;i<=cnt;i++){
int l=mp[i].l,r=mp[i].r,w=mp[i].w;
int fl=find(l),fr=find(r);
if(fl!=fr){
fa[fl]=fr;
tot++;
ma=max(ma,w);
}
}
cout<<tot<<" "<<ma;
return 0;
}
4.
accoders的【一本通图 最小生成树】联络员(liaison)2026
思路:
先将必选选入，然后从小到大做非必选的最小生成树即可。
code:
[Kruskal]
#include<bits/stdc++.h>
using namespace std;
int fa[2001*2001],cnt;
struct node{
int l,r,w,fl;
bool operator <(const node &W)const{
return w<W.w;
}
}mp[2001*2001];
int find(int x){
if(x==fa[x]){
return x;
}
return fa[x]=find(fa[x]);
}
int main(){
int n,m;
cin>>n>>m;
int tot=0,ans=0;
for(int i=1;i<=m;i++){
int l,r,w,f;
cin>>f>>l>>r>>w;
mp[++cnt]={l,r,w,f};
}
for(int i=1;i<=n;i++){
fa[i]=i;
}
sort(mp+1,mp+cnt+1);
for(int i=1;i<=cnt;i++){
int l=mp[i].l,r=mp[i].r,w=mp[i].w,f=mp[i].fl;
int fl=find(l),fr=find(r);
if(f==1){
fa[fl]=fr;
ans+=w;
tot++;
}
}
for(int i=1;i<=cnt;i++){
int l=mp[i].l,r=mp[i].r,w=mp[i].w,f=mp[i].fl;
int fl=find(l),fr=find(r);
if(fl!=fr&&f==2){
fa[fl]=fr;
ans+=w;
tot++;
}
}
cout<<ans;
return 0;
}
5.
accoders 的【一本通图 最小生成树】 连接格点2098
思路:
通过类似hash的操作将格点强行建边，
把给的边放入边数组中，然后跑一遍最小生成树。
code(感谢little_sheep_2024的code):
#include<bits/stdc++.h>
using namespace std;
int m,n,f[1000005];
int x,xx,y,yy,idx=0;
struct edge{
int u,v,w;
}e[5000005];
int find(int u){
return f[u]==u ? u : f[u]=find(f[u]);
}
int fe(int x,int y){
return m*(x-1)+y;
}
bool cmp(edge x,edge y){
return x.w<y.w;
}
int kruscal(){
int ans=0;
sort(e+1,e+idx+1,cmp);
for(int i=1;i<=idx;i++){
int fu=find(e[i].u);
int fv=find(e[i].v);
if(fu!=fv){
ans+=e[i].w;
f[fu]=fv;
}
}
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n*m;i++){
f[i]=i;
}
while(cin>>x>>y>>xx>>yy){
int fu=find(fe(x,y));
int fv=find(fe(xx,yy));
f[fu]=fv;
}
for(int i=1;i<m;i++){
for(int j=1;j<=n;j++){
e[++idx].u=fe(j,i),e[idx].v=fe(j,i+1);
e[idx].w=2;
}
}
for(int i=1;i<n;i++){
for(int j=1;j<=m;j++){
e[++idx].u=fe(i,j),e[idx].v=fe(i+1,j);
e[idx].w=1;
}
}
cout<<kruscal();
return 0;
}
6.
accoders的【一本通提高篇最小生成树】新的开始2098
思路:
将建设发电机的费用变成一个点放在原本的图外，
这样建设发电机就变成了连一个费用为V的边，
然后就成了一个大图的最小生成树。
code:
[Kruskal]
#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int n;
struct node{
int l,r,w;
bool operator <(const node &W) const{
return w<W.w;
}
}mp[N];
int cnt,fa[N];
int find(int x){
if(fa[x]==x){
return x;
}
return fa[x]=find(fa[x]);
}
int main(){
cin>>n;
for(int i=1;i<=n+1;i++){
fa[i]=i;
}
for(int i=1;i<=n;i++){
int v;
cin>>v;
mp[++cnt]={i,n+1,v};
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int w;
cin>>w;
if(i<j){
mp[++cnt]={i,j,w};
}
}
}
sort(mp+1,mp+cnt+1);
int tot=0,ans=0;
for(int i=1;i<=cnt;i++){
int l=mp[i].l,r=mp[i].r,w=mp[i].w;
int fl=find(l),fr=find(r);
if(fl!=fr){
fa[fl]=fr;
ans+=w;
tot++;
}
if(tot>=n){
break;
}
}
cout<<ans;
return 0;
}