zoj 1586

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1586

//zoj 1586

#include<iostream>

#include<cstdio>

using namespace std;

#define N 1005

int a[N][N],low[N],n,ans;

int b[N];

int min(int x,int y)

{    return x<y?x:y;   }

void prim(int u0)

{

    int i,j,m,k;

    ans=0;

    for (i=1;i<n;i++)  low[i]=a[u0][i];

    low[u0]=-1;

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

    {

        m=1<<20;

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

            if (low[j]!=-1&&low[j]<m)

            {    m=low[j];    k=j;   }

        ans+=m;

        low[k]=-1;

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

            if (low[j]!=-1)low[j]=min(low[j],a[k][j]);

    }

}

int main()

{

   int i,j,t;

   scanf("%d",&t);

   while(t--)

   {

      scanf("%d",&n);

      for(i=0;i<n;i++)  scanf("%d",&b[i]);

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

      {

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

         {

            scanf("%d",&a[i][j]);

            a[i][j]+=b[i]+b[j];

         }

      }

      prim(0);

      cout<<ans<<endl;

   }

   return 0;

}

***************************************************************************************************

#include<iostream>

#include<cstdio>

using namespace std;

#define N 1005

int a[N][N],low[N],n,ans;

int b[N];

int min(int x,int y)

{    return x<y?x:y;   }

void prim(int u0)

{

    int i,j,m,k;

    ans=0;

    for (i=1;i<n;i++)  low[i]=a[u0][i];

    low[u0]=-1;

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

    {

        m=1<<20;

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

            if (low[j]!=-1&&low[j]<m)

            {    m=low[j];    k=j;   }

        ans+=m;

        low[k]=-1;

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

            if (low[j]!=-1)low[j]=min(low[j],a[k][j]);

    }

}

int main()

{

   int i,j,t;

   scanf("%d",&t);

   while(t--)

   {

      scanf("%d",&n);

      for(i=0;i<n;i++)  scanf("%d",&b[i]);

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

      {

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

         {

            scanf("%d",&a[i][j]);

            if(i=j)   a[i][j]=1<<20;    //对角线

           else a[i][j]+=b[i]+b[j];

         }

      }

      prim(0);

      cout<<ans<<endl;

   }

   return 0;

}

**************************************************************************888

#include<iostream>

#include<cstdio>

using namespace std;

#define N 1005

#define INF 1000000

int a[N][N],low[N],n,ans;

int b[N];

int min(int x,int y)

{    return x<y?x:y;   }

void prim(int u0)

{

    int i,j,m,k;

    ans=0;

    for (i=1;i<n;i++)  low[i]=a[u0][i];

    low[u0]=-1;

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

    {

        m=1<<20;

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

            if (low[j]!=-1&&low[j]<m)

            {    m=low[j];    k=j;   }

        ans+=m;

        low[k]=-1;

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

            if (low[j]!=-1)low[j]=min(low[j],a[k][j]);

    }

}

int main()

{

   int i,j,t;

   scanf("%d",&t);

   while(t--)

   {

      scanf("%d",&n);

      for(i=0;i<n;i++)  scanf("%d",&b[i]);

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

      {

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

         {

            scanf("%d",&a[i][j]);

            if(i=j)   a[i][j]=INF;    //对角线

           else a[i][j]+=b[i]+b[j];

         }

      }

      prim(0);

      cout<<ans<<endl;

   }

   return 0;

}