喵哈哈村的修路游戏

题目链接http://www.qscoj.cn/problem/53/

题意:略。

思路:相当于求最小生成树,已连接好的边权值设为0即可。

#include <bits/stdc++.h>
using namespace std;
const int maxn=100+5;
struct Edge{
    int u,v,w;
    Edge(int _,int __,int ___):u(_),v(__),w(___){}
    bool operator <(const Edge&rhs) const{
        return w<rhs.w;
    }
};
int n,m,fa[maxn];
vector<Edge>edges;
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
int main(){
    while (~scanf("%d%d",&n,&m)){
        edges.clear();
        for (int i=1;i<=m;i++){
            int u,v;scanf("%d%d",&u,&v);
            edges.push_back(Edge(u,v,0));
        }
        for (int i=1;i<=n;i++){
            fa[i]=i;
            for (int j=i+1;j<=n;j++){
                edges.push_back(Edge(i,j,1));
            }
        }
        sort(edges.begin(),edges.end());
        int ans=0,cnt=0;
        for (auto& e:edges){
            int u=e.u,v=e.v;
            int tu=Find(u),tv=Find(v);
            if (tu!=tv){
                fa[tu]=tv;
                ans+=e.w;
                if (++cnt>=n-1) break;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注