1102.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 49 行

#include<iostream.h>
#include<string>
int a[101][101],min;
bool s[101];
int i_index,j_index;
int len;
int main()
{
    int n,i,j,k,m,t;
    while(cin>>n){
        memset(a,0,sizeof(a));
        memset(s,0,sizeof(s));
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                cin>>a[i][j];
        cin>>m;
        while(m--){
            cin>>i>>j;
            a[i][j]=0;
            a[j][i]=0;
        }
        min=10000;len=0;
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                if(i!=j&&a[i][j]<min){
                    min=a[i][j];
                    i_index=i;
                    j_index=j;
                }
        s[i_index]=true;
        s[j_index]=true;
        len+=min;
        for(k=0;k<n-2;k++){
            min=10000;
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                    if(i!=j&&a[i][j]<min&&s[i]==true&&s[j]==false){
                        min=a[i][j];
                        i_index=i;
                        j_index=j;
                    }
            len+=min;
            s[j_index]=true;
        }
        cout<<len<<endl;
    }
    return 0;
}