最小生成树

Kruskal算法

将图中的每条边按照权值从小到大排序，然后再贪心地用并查集去联合。具体的就是看每条边的两个点的并查集祖先是否是同一个，不是就联合。当我们找到了\(n-1\)条边的时候就可以跳出循环了。

代码如下：

#include <bits/stdc++.h>

using namespace std;

const int MAXN=5e3+22;

struct edge{
    int u,v,w;
    bool operator<(edge other)const{
        return w<other.w;
    } 
};

vector<edge> e;
int n,m,fa[MAXN],ans;

int find(int x){
    return fa[x]==x?x:fa[x]=find(fa[x]);
}

void unite(int u,int v){
    int f_u=find(u),f_v=find(v);
    fa[f_u]=f_v;
}

void kruskal(){
    for(int i=1;i<=n;++i){
        fa[i]=i;
    }
    for(auto ed:e){
        int u=ed.u,v=ed.v,w=ed.w;
        if(find(u)!=find(v)){
            unite(u,v);
            ans+=w;
        }
    }
    int uf=find(1),flag=1;
    for(int i=2;i<=n;++i){
        if(uf!=find(i)){
            flag=0;
        }
    }
    if(flag)cout<<ans<<endl;
    else cout<<"orz"<<endl;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        e.push_back({u,v,w});
    }
    sort(e.begin(),e.end(),less<edge>());
    kruskal();
    return 0;
}

Prim算法

dijkstra算法的变种，蒟蒻没咋用过

#include <bits/stdc++.h>

using namespace std;

const int MAXN=5e3+22;
const int INF=0x3f3f3f3f;

struct node{
    int u,dis;
    node(int _u,int _dis):u(_u),dis(_dis){}
    bool operator>(const node& other)const{return dis>other.dis;}
};

struct edge{
    int v,w;
};

vector<edge> p[MAXN];
priority_queue<node,vector<node>,greater<node>> pq;
int n,m,dis[MAXN],vis[MAXN];

inline void add(int u,int v,int w){
    p[u].push_back({v,w});
    p[v].push_back({u,w});
}

int prim(int s){
    int ret=0;
    for(int i=1;i<=n;++i)dis[i]=INF;
    dis[s]=0;
    pq.push({s,0});
    while(!pq.empty()){
        int u=pq.top().u,dist=pq.top().dis;
        pq.pop();
        if(vis[u])continue;
        vis[u]=1;
        ret+=dist;
        for(auto edge:p[u]){
            int v=edge.v,w=edge.w;
            if(w<dis[v]){
                dis[v]=w;
                pq.push({v,dis[v]});
            }
        }
    }
    return ret;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        add(u,v,w);
    }
    int ans=prim(1),flag=1;
    for(int i=1;i<=n;++i){
        if(!vis[i])flag=0;
    }
    if(flag)
    cout<<ans<<endl;
    else
    cout<<"orz"<<endl;
    return 0;
}

次小生成树

次小生成树分为严格的和不严格的，这里给出严格的代码，不严格的就只有一小点判断的改动。

方法是先找出最小生成树，建立最小生成树。然后倍增维护最小生成树的祖先，路径上的最大权值，次大权值。

最后在看所有的非最小生成树的边的两点在最小生成树中的路径上的最大值是多少，并且与未使用的该边替换，更新答案。如果最大值等于未使用的该边的权值，那么直接找次大值替换。

最后的答案等于所有替换方案的最小值。

代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e5+2;
const int MAXM=3e5+2;
const int INF=0x7fffffffffffffff;

struct Tr{
private:
    struct edge{
        int v,w;
    };
    vector<edge> p[MAXN];
    int fa[MAXN][31],dep[MAXN],m[MAXN][31],mm[MAXN][31];

public:
    void add(int u,int v,int w){
        p[u].push_back({v,w});
        p[v].push_back({u,w});
    }

    void dfs(int x,int fno){
        if(fno)dep[x]=dep[fno]+1,fa[x][0]=fno,mm[x][0]=-INF;

        for(int i=1;i<=30;++i){
            fa[x][i]=fa[fa[x][i-1]][i-1];
            int tmp[4]={m[x][i-1],m[fa[x][i-1]][i-1],
                        mm[x][i-1],mm[fa[x][i-1]][i-1]};
            sort(tmp,tmp+4);
            m[x][i]=tmp[3];
            int ptr=2;
            for(;ptr>=0&&tmp[ptr]==tmp[3];){--ptr;}
            mm[x][i]=ptr==-1?-INF:tmp[ptr];
        }

        for(auto& edge:p[x]){
            int v=edge.v,w=edge.w;
            if(v==fno)continue;
            m[v][0]=w;
            dfs(v,x);
        }
    }

    int lca(int x,int y){
        if(dep[x]>dep[y])swap(x,y);
        for(int i=30;i>=0;--i){
            if(dep[fa[y][i]]>=dep[x])y=fa[y][i];
        }
        if(x==y)return x;
        for(int i=30;i>=0;--i){
            if(fa[x][i]!=fa[y][i]){
                x=fa[x][i],y=fa[y][i];
            }
        }
        return fa[x][0];
    }

    int query(int x,int y,int w){
        int ret=-INF;
        for(int i=30;i>=0;--i){
            if(dep[fa[x][i]]>=dep[y]){
                if(w!=m[x][i])
                    ret=max(ret,m[x][i]);
                else
                    ret=max(ret,mm[x][i]);
                x=fa[x][i];
            }
        }
        return ret;
    }
};

Tr tr;

struct _edge_{
    int u,v,w;
    bool operator<(const _edge_& other)const{return w<other.w;} 
};

vector<_edge_> edges;
int fa[MAXN],n,m,used[MAXM];

int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void unite(int u,int v){int fu=find(u),fv=find(v);if(fu!=fv)fa[fu]=fv;}

int kruskal(){
    int ans=0,cnt=0;
    for(int i=1;i<=n;++i)fa[i]=i;
    sort(edges.begin(),edges.end());
    for(int i=0;i<edges.size();++i){
        _edge_ e=edges[i];
        int u=e.u,v=e.v,w=e.w;
        if(find(u)!=find(v)){
            unite(u,v);
            ans+=w,++cnt;
            used[i]=1;
            tr.add(u,v,w);
        }
        if(cnt==n-1)break;
    }
    return ans;
}

signed main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v,w;cin>>u>>v>>w;
        edges.push_back({u,v,w});
    }
    int ans_1=kruskal(),ans_2=INF;
    tr.dfs(1,0);
    for(int i=0;i<edges.size();++i){
        if(!used[i]){
            int u=edges[i].u,v=edges[i].v,w=edges[i].w;
            int _lca=tr.lca(u,v);
            int tmp1=tr.query(u,_lca,w);
            int tmp2=tr.query(v,_lca,w);
            int _m=max(tmp1,tmp2);
            if(_m>-INF)
            ans_2=min(ans_2,ans_1-_m+w);
        }
    }
    if(ans_2!=INF)cout<<ans_2<<endl;
    else cout<<-1<<endl;
}