记录编号	186683	评测结果	AAAAAAAAAA
题目名称	[USACO Oct08] 挖水井	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.059 s
提交时间	2015-09-14 18:19:52	内存使用	1.46 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
const int inf=1061109567;
const int maxn=100010;
const int maxm=310;
const int mod=10007;

struct node
{
    int u,v,w;
    bool operator < (const node &a) const {
        return w<a.w;
    }
} m[maxn];

int p[maxm];
int cnt=1;int n;

int found(int x) {return (p[x]==x) ? x : p[x]=found(p[x]);}

void kruskal()
{
    sort(m+1,m+cnt);
    int ans=0;
    for(int i=1;i<cnt;i++)
    {
        int x=found(m[i].u);
        int y=found(m[i].v);
        if(x!=y)
        {
            ans+=m[i].w;
            p[x]=y;
        }
    }
    printf("%d\n",ans);
}

int main()
{
    freopen("water.in","r",stdin);
    freopen("water.out","w",stdout);
    //clock_t st=clock();
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&m[cnt].w);
        m[cnt].u=i;m[cnt].v=n+1;
        cnt++;m[cnt].w=m[cnt-1].w;
        m[cnt].u=n+1;m[cnt].v=i;
        cnt++;p[i]=i;
    }
    p[n+1]=p[n+1];
    int a;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a);
            if(i==j) continue;
            m[cnt].u=i;m[cnt].v=j;
            m[cnt].w=a;
            cnt++;
        }
    }
    kruskal();
    //clock_t ed=clock();
    //printf("\nTime used : %.7lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}