poj1287 Networking【最小生成树】

网络安全邮递员 lv.1

发布时间：2022-12-04 12:12:41 290

相关标签：

题目链接：http://poj.org/problem?id=1287
题意：类似n个点，m条边，每条边需要花费一定的代价才能联通，问你把n个点联通的最小花费
解析：最小生成树裸题

#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 1e5+100;
struct node
{
    int x,y,v;
    bool operator < (const node &b)const
    {
        return v<b.v;
    }
}a[maxn];
int fa[maxn];
void init(int n)
{
    for(int i=0;i<=n;i++)
        fa[i] = i;
}
int getfa(int x)
{
    if(x==fa[x])
        return x;
    return fa[x] = getfa(fa[x]);
}
int main(void)
{
    int n,m;
    while(~scanf("%d",&n)&&n)
    {
        scanf("%d",&m);
        init(n);
        for(int i=0;i<m;i++)
            scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].v);
        sort(a,a+m);
        int ans = 0;
        for(int i=0;i<m;i++)
        {
            int t1 = getfa(a[i].x);
            int t2 = getfa(a[i].y);
            if(t1!=t2)
            {
                fa[t1] = t2;
                ans += a[i].v;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

文章来源： https://blog.51cto.com/u_11435021/5880118

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。