算法总结—生成树1

LRRabcd · 2024-09-12 20:44:09 · 算法·理论

生成树

生成树的定义

把一个无向带权联通图，删掉一部分边后变成了一棵树，删边的过程就叫生成树。

那么生成树一共需要删多少条边呢？

我们设一张无向带权联通图有 n 个点 m 条边，生成树时并不能删点，所以他会生成一棵 n 点 n-1 条边的树，这样就会删除 m-n+1 条边。

实现最小生成树

要使得边权总和尽可能的小，我们要给边权从小到大拍个序，每次选最小的边权进行连边，不过有一种情况不可以连边：环，所以我们还需要用并查集判环。

根据上面步骤实现生成树时间复杂度 O(m\log m+m) ，这个算法名为 \text{Kruskal} 。

P3366 【模板】最小生成树

按上述方法写即可，主要是我们如何判断不连通，再连边时，可以用一个变量来记录边的数量，当跑完一遍 \text{Kruskal} 时，再比较边的数量与 n-1 的大小即可：边的数量大于等于 n-1 联通，边的数量小于 n-1 不联通。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct node{
    int u,v;
    int w;
}a[200005];
bool cmp(node q,node h){
    return q.w<h.w; 
}
int father[5005];
int find(int x){
    if(father[x]==x){
        return x;
    } 
    father[x]=find(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        father[x]=y;
    }
    return;
}
void init(){
    for(int i=1;i<=n;i++){
        father[i]=i;
    } 
    return;
}
int ans=0,cnt=0;
void Kruskal(){
    for(int i=1;i<=m;i++){
        if(cnt==n-1){
            break;
        }
        int u=find(a[i].u);
        int v=find(a[i].v);
        if(u!=v){
            union1(u,v);
            ans+=a[i].w;
            cnt++;
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
    } 
    sort(a+1,a+1+m,cmp);
    init();
    Kruskal();
    if(cnt<n-1){
        cout<<"orz";
        return 0;
    }
    cout<<ans;
    return 0;
}

P2820 局域网

在模板基础上用所有边权之和减去即可。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct node{
    int u,v;
    int w;
}a[10005];
bool cmp(node q,node h){
    return q.w<h.w; 
}
int father[105];
int find(int x){
    if(father[x]==x){
        return x;
    } 
    father[x]=find(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        father[x]=y;
    }
    return;
}
void init(){
    for(int i=1;i<=n;i++){
        father[i]=i;
    } 
    return;
}
int ans=0;
void Kruskal(){
    int cnt=0;
    for(int i=1;i<=m;i++){
        if(cnt==n-1){
            break;
        }
        int u=find(a[i].u);
        int v=find(a[i].v);
        if(u!=v){
            union1(u,v);
            ans+=a[i].w;
            cnt++;
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    int cnt=0;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
        cnt+=a[i].w;
    } 
    sort(a+1,a+1+m,cmp);
    init();
    Kruskal();
    cout<<cnt-ans;
    return 0;
}

P1195 口袋的天空

树有 n 个点，n-1 条边，所以在树上每连一条边连通块数量就会减一，没在树上删一条边连通块数量加一，有了这个结论，这题就简单了，要想有 k 个连通块，只用连 n-k 条边。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m,k;
struct node{
    int u,v;
    int w;
}a[200005];
bool cmp(node q,node h){
    return q.w<h.w; 
}
int father[5005];
int find(int x){
    if(father[x]==x){
        return x;
    } 
    father[x]=find(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        father[x]=y;
    }
    return;
}
void init(){
    for(int i=1;i<=n;i++){
        father[i]=i;
    } 
    return;
}
int ans=0,cnt=0;
void Kruskal(){
    for(int i=1;i<=m;i++){
        if(cnt==n-k){
            break;
        }
        int u=find(a[i].u);
        int v=find(a[i].v);
        if(u!=v){
            union1(u,v);
            ans+=a[i].w;
            cnt++;
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
    } 
    sort(a+1,a+1+m,cmp);
    init();
    Kruskal();
    if(cnt<n-k){
        cout<<"No Answer";
        return 0;
    }
    cout<<ans;
    return 0;
}

P1194 买礼物

这道题有两种解法。

1.

每次按照更优的方案建边，如果 K_{i,j} 不等于 0 且 K_{i,j}<A 则按 K_{i,j} 建边，否则按照 A 建边。然后正跑一遍 \text{Kruskal} 。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct node{
    int u,v;
    int w;
}a[250005];
bool cmp(node q,node h){
    return q.w<h.w; 
}
int father[250005];
int find(int x){
    if(father[x]==x){
        return x;
    } 
    father[x]=find(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        father[x]=y;
    }
    return;
}
void init(){
    for(int i=1;i<=m;i++){
        father[i]=i;
    } 
    return;
}
int ans;
void Kruskal(){
    int cnt=0;
    for(int i=1;i<=m*m;i++){
        if(cnt==m-1){
            break;
        }
        int u=find(a[i].u);
        int v=find(a[i].v);
        if(u!=v){
            union1(u,v);
            ans+=a[i].w;
            cnt++;
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            a[(i-1)*m+j]={i,j,(x<n&&x!=0)?x:n};
        }
    } 
    sort(a+1,a+1+m*m,cmp);
    init();
    ans=n;
    Kruskal();
    cout<<ans;
    return 0;
}

2.

按照 K_{i,j} 建边，除非 K_{i,j}=0 。我们还需要一个虚点 0 ，并把 0 与其他所有点连起来，边权为 A 。这样会节省许多空间。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct node{
    int u,v;
    int w;
}a[250005];
int k=0;
bool cmp(node q,node h){
    return q.w<h.w; 
}
int father[250005];
int find(int x){
    if(father[x]==x){
        return x;
    } 
    father[x]=find(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        father[x]=y;
    }
    return;
}
void init(){
    for(int i=1;i<=m;i++){
        father[i]=i;
    } 
    return;
}
int ans;
void Kruskal(){
    int cnt=0;
    for(int i=1;i<=k;i++){
        if(cnt==m-1){
            break;
        }
        int u=find(a[i].u);
        int v=find(a[i].v);
        if(u!=v){
            union1(u,v);
            ans+=a[i].w;
            cnt++;
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            int x;
            cin>>x;
            if(x>0){
                a[++k]={i,j,x};
            }
        }
    } 
    for(int i=1;i<=m;i++){
        a[++k]={0,i,n};
    }
    sort(a+1,a+1+k,cmp);
    init();
    ans=n;
    Kruskal();
    cout<<ans;
    return 0;
}

P2330 [SCOI2005] 繁忙的都市

这题怎么看都不像是最小生成树，因为他是瓶颈生成树，瓶颈生成树与最小生成树的区别就在瓶颈生成树是取边权最大的作为答案，但是这一道题用最小生成树的模板交上去也能 AC 。这样就会得到一个结论：最小生成树一定是瓶颈生成树，不过瓶颈生成树不一定是最小生成树。

代码

#include<iostream>
#include<algorithm>
using namespace std;
int n,m;
struct node{
    int u,v;
    int w;
}a[8005];
bool cmp(node q,node h){
    return q.w<h.w; 
}
int father[305];
int find(int x){
    if(father[x]==x){
        return x;
    } 
    father[x]=find(father[x]);
    return father[x];
}
void union1(int x,int y){
    x=find(x);
    y=find(y);
    if(x!=y){
        father[x]=y;
    }
    return;
}
void init(){
    for(int i=1;i<=n;i++){
        father[i]=i;
    } 
    return;
}
int cnt=0;
int Max=-1e9;
void Kruskal(){
    for(int i=1;i<=m;i++){
        if(cnt==n-1){
            break;
        }
        int u=find(a[i].u);
        int v=find(a[i].v);
        if(u!=v){
            union1(u,v);
            cnt++;
            Max=max(Max,a[i].w);
        }
    }
    return;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i].u>>a[i].v>>a[i].w;
    } 
    sort(a+1,a+1+m,cmp);
    init();
    Kruskal();
    cout<<cnt<<" "<<Max;
    return 0;
}