Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000). Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).

Determine the minimum amount Farmer John will have to pay to water all of his pastures.

• Line 1: A single integer: N
• Lines 2..N + 1: Line i+1 contains a single integer: W_i
• Lines N+2..2N+1: Line N+1+i contains N space-separated integers; the j-th integer is P_ij

• Line 1: A single line with a single integer that is the minimum cost of providing all the pastures with water.

INPUT DETAILS:

There are four pastures. It costs 5 to build a well in pasture 1,4 in pastures 2 and 3, 3 in pasture 4. Pipes cost 2, 3, and 4depending on which pastures they connect.

OUTPUT DETAILS:

Farmer John may build a well in the fourth pasture and connect each pasture to the first, which costs 3 + 2 + 2 + 2 = 9.

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 using namespace std;

 #define MAXN 300+5

 #define MAXM 90000

 int n,m,F[MAXN],Vis[MAXN];

 struct edge

 {

     int u,v,w;

 }edges[MAXM];

 int Find(int x)

 {

     return F[x]==-?x:F[x]=Find(F[x]);

 }

 bool cmp(edge a,edge b)

 {

     return a.w<b.w;

 }

 int Kruskal()

 {

     memset(F,-,sizeof(F));

     sort(edges,edges+m,cmp);

     int ans=,cnt=,u,v,w,fx,fy;

     for(int i=;i<m;i++)

     {

         u=edges[i].u;

         v=edges[i].v;

         w=edges[i].w;

         fx=Find(u);

         fy=Find(v);

         if(fx!=fy)

         {

             ans+=w;

             cnt++;

             F[fx]=fy;

         }

         if(cnt==n)break;//连通田n-1条边，加井1条边

     }

     return ans;

 }

 void addedges(int u,int v,int w)

 {

     edges[m].u=u;

     edges[m].v=v;

     edges[m++].w=w;

 }

 int main()

 {

     int w;

     scanf("%d",&n);

     for(int i=;i<=n;i++)

     {

         scanf("%d",&w);

         addedges(,i,w);

     }

     for(int i=;i<=n;i++)

     {

         for(int j=;j<=n;j++)

         {

             scanf("%d",&w);

             if(i>=j)continue;

             addedges(i,j,w);

         }

     }

     int ans=Kruskal();

     printf("%d\n",ans);

     return ;

 }