1258.cpp

来自「这些是我到目前在PKU上做出的题目」· C++ 代码 · 共 45 行

#include <stdio.h>
int main(void)
{		
    int n,i,j,origin[100][100],opt[100],sum=0,max_distance=0,min,vertex;
    bool flag[100];
    while(scanf("%d",&n)!=EOF)
    {
        sum=0;
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            {
                scanf("%d",&origin[i][j]);
                if(origin[i][j]>max_distance)
                    max_distance=origin[i][j];
            }
        }
        for(i=0;i<n;i++)
            opt[i]=origin[0][i];
        flag[0]=true;
        for(i=1;i<n;i++)
            flag[i]=false;
        for(i=1;i<n;i++)
        {
            min=max_distance+1;
            for(j=0;j<n;j++)
            {
                if(!flag[j]&&min>opt[j])
                {
                    min=opt[j];
                    vertex=j;
                }
            }	
            sum+=min;
            flag[vertex]=true;
            for(j=0;j<n;j++)
            {
                if(!flag[j])
                    opt[j]=origin[j][vertex]>opt[j]?opt[j]:origin[j][vertex];
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}