解题报告 P1546 最短网络 Agri-Net

题目内容

FJ 已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接所有的农场。

你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距离不会超过 10^5。

解题思路

农场之间要联通，使得光缆最小，所以要用最小生成树，跑一遍 Kruskal 就可以了。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

const int maxn=105;

struct unionset
{
    int bin[maxn];
    unionset()
    {
        for(int i=1;i<=maxn;i++)
            bin[i]=i;
    }
    int anc(int x)
    {
        if(bin[x]!=x)
            return bin[x]=anc(bin[x]);
        return bin[x];
    }
    void uni(int x,int y)
    {
        bin[anc(x)]=anc(y);
    }
    bool query(int x,int y)
    {
        return anc(x)==anc(y);
    }
}u;

struct edge
{
    int from,to,dist;
    edge(){}
    edge(int _from,int _to,int _dist)
    {
        this->from=_from;
        this->to=_to;
        this->dist=_dist;
    }
};

int n;
vector<edge> v;

bool cmp(edge a,edge b)
{
    return a.dist<b.dist;
}

int kruskal()
{
    int ans=0;
    sort(v.begin(),v.end(),cmp);
    for(auto e:v)
    {
        if(!u.query(e.from,e.to))
        {
            u.uni(e.from,e.to);
            ans+=e.dist;
        }
    }
    return ans;
}

int main()
{
    scanf("%d",&n);
    int tmp;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&tmp);
            if(tmp)
                v.push_back(edge(i,j,tmp));
        }
    printf("%d\n",kruskal());
    return 0;
}