[BZOJ1601][Usaco2008 Oct]灌水 kruskal


原题
给定n块土地,可以连接两块土地,也可以在某块土地上建立水库,要求每块土地都能用上水.求最小花费.

事实上就是给了一个完全图,要求每个点都与有水库的点连通.我们发现建水库的花销很烦人,于是考虑新建一个虚拟水源,每个点建立水库的花销就当做是和水源连边的花销.求一遍最小生成树就是答案.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 2333
#define M 233333
using namespace std;
int n;
struct Node
{
    int x,y,z;
}e[M];
int tot;
inline bool cmp(Node a,Node b)
{
    return a.z<b.z;
}
int fa[N];
int find(int x)
{
    if(x==fa[x])return x;
    return fa[x]=find(fa[x]);
}
int ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        scanf("%d",&e[++tot].z);
        e[tot].x=i,e[tot].y=n+1;
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&e[++tot].z);
            e[tot].x=i,e[tot].y=j;
        }
    }
    sort(e+1,e+tot+1,cmp);
    for(int dx,dy,i=1;i<=tot;i++)
    {
        dx=find(e[i].x),dy=find(e[i].y);
        if(dx!=dy)fa[dy]=dx,ans+=e[i].z;
    }
    cout<<ans;
    return 0;
}

发表评论

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