1863.cpp

杭电 acm部分代码 有兴趣的可以下载 谢谢

#include<stdio.h>
#include<string>
int a[110][110];
bool hash[110];
bool visit[110];
int m,n;
void dfs(int x){
    int i;
    for(i=1;i<=m;i++){
        if(a[x][i]!=0&&visit[i]==false){
            visit[i]=true;
            dfs(i);
        }
    }
}
bool tong(){
    int i;
    visit[1]=true;
    dfs(1);
    for(i=1;i<=m;i++)
        if(visit[i]==false)
            return false;
    return true;
}
int mst(){
    int i,j,k;
    int index_i,index_j;
    int dis=-1,lest=0;
    for(i=1;i<=m;i++)
        for(j=1;j<=m;j++)
            if(i!=j&&a[i][j]!=0&&(dis==-1||(dis>0&&dis>a[i][j]))){
                index_i=i;
                index_j=j;
                dis=a[i][j];
            }
    hash[index_i]=true;
    hash[index_j]=true;
    lest+=dis;
    for(k=1;k<m-1;k++){
        dis=-1;
        for(i=1;i<=m;i++)
            for(j=1;j<=m;j++)
                if(hash[i]==true&&hash[j]==false&&i!=j&&a[i][j]!=0&&(dis==-1||dis>0&&dis>a[i][j])){
                    index_i=i;
                    index_j=j;
                    dis=a[i][j];
                }
        hash[index_j]=true;
        lest+=dis;
    }
    return lest;
}
int main()
{
    int i;
    while(scanf("%d %d",&n,&m)==2&&n){
        memset(a,0,sizeof(a));
        memset(hash,0,sizeof(hash));
        memset(visit,0,sizeof(visit));
        int s;
        int p,q,c=n;
        while(c--){
            scanf("%d %d %d",&p,&q,&s);
            a[p][q]=s;
            a[q][p]=s;
        }
        if(tong()==false)
            printf("?\n");
        else
            printf("%d\n",mst());
    }
    return 0;
}