BZOJ 1601 [Usaco2008 Oct]灌水

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1601

题意:Farmer John已经决定把水灌到他的n\left(1\leq n \leq 300\right)块农田,农田被数字1n标记。把一块土地进行灌水有两种方法,从其他农田饮水,或者这块土地建造水库。 建造一个水库需要花费w_{i}\left(1\leq w_{i}\leq 100000\right),连接两块土地需要花费p_{ij}(1\leq p_{ij}\leq 100000,p_{ij}=p_{ji},p_{ii}=0). 计算Farmer John所需的最少代价。

思路:首先想想最后答案一定是呈森林状,每个集合里都是一颗最小生成树,这样一看似乎不可解但是我们可以建立一个超级源点连向每个点,边权为每个点的点权,那么我们就消除了点权对决策的影响,这时候跑一下最小生成树就可以了。

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=300+5;
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
struct Edge{
    int u,v,w;
    Edge(int _,int __,int ___):u(_),v(__),w(___){}
    bool operator<(const Edge&b)const{
        return w<b.w;
    }
};
int n,x;
int w[maxn],fa[maxn];
vector<Edge>edges;
int Find(int x){return fa[x]==x?x:fa[x]=Find(fa[x]);}
int main(){
    read(n);
    fa[0]=0;
    for (int i=1;i<=n;i++) read(w[i]),fa[i]=i;
    for (int i=1;i<=n;i++){
        edges.push_back(Edge(0,i,w[i]));
    }
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            read(x);
            if (i>j){
                edges.push_back(Edge(i,j,x));
            }
        }
    }
    int ans=0,cnt=0;
    sort(edges.begin(),edges.end());
    for (int i=0;i<(int)edges.size();i++){
        Edge &e=edges[i];
        int u=e.u,v=e.v;
        int tx=Find(u),ty=Find(v);
        if (tx!=ty){
            fa[tx]=ty;
            ans+=e.w;
            if (++cnt>=n) break;
        }
    }
    printf("%d\n",ans);
    return 0;
}

发表评论

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