BZOJ-1601: [Usaco2008 Oct]灌水

Description

有n块农田，每个农田修建水库有一定代价，向别的有水农田引水也有一定的代价。询问最小代价使得所有农田都有水。n<=300

脑袋里各种最小割，费用流在奔腾。各种发现图建的不对，最后发现不能做。
默默地躺在床上怀疑人生，想一想：这题。。。网络流的贪心策略的不对啊。。。需要的是每条边的代价，然后流量还不能够乘以代价。不就是每条边有花费，然后选最小花费使得全图和汇点联通。。。等等？？？联通？？最小花费？？边权？？
这tm不是最小生成树吗？？？天是蓝的，大地是绿的，答案是连有汇点的最小生成树的。
。。。被自己蠢哭。。。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,fa[310],cnt,ans;
struct node
{
    int x,y,f;
}a[100000];
bool cmp(node x,node y)
{
    return x.f<y.f;
}
int find(int x)
{
    return fa[x]==x? x: fa[x]=find(fa[x]);
}
int main()
{
    scanf("%d",&n);int x;
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[++cnt].f);
        a[cnt].x=i; a[cnt].y=n+1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&x);
            if(i<j)
            {
                a[++cnt].f=x;
                a[cnt].x=i;
                a[cnt].y=j;
            }
        }
    sort(a+1,a+cnt+1,cmp);
    n++;int dx,dy,tmp=0;
    for(int i=1;i<=cnt;i++)
    {
        dx=find(a[i].x);
        dy=find(a[i].y);
        if(dx!=dy)
        {
            ans+=a[i].f;
            fa[dx]=dy;
            tmp++;
            if(tmp==n) break;
        }
    }
    printf("%d",ans);
    return 0;
}