1233.txt

来自「1235 杭州电子科技大学acm代码即可将会计科」· 文本 代码 · 共 63 行

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

struct Node
{
    int adjvex;
    int cost;
};

const int Max=101;
Node road[Max][Max];
int prim[Max];
bool v[Max];

int MST_Prim(int n)
{
    int i,j,k,now,lowcost,min;
    
    now=1;lowcost=0;v[1]=true;
    for(i=road[1][0].adjvex;i>0;i--)
        prim[ road[1][i].adjvex ]=road[1][i].cost;
        
    for(i=1;i<n;i++)
    {
        for(j=1,min=prim[0];j<Max;j++)
            if(min>prim[j])
            {   min=prim[j];now=j;}
        lowcost+=min;
        prim[now]=9999;
        v[now]=true;
        for(j=road[now][0].adjvex;j>0;j--)
            if(!v[road[now][j].adjvex] && prim[ road[now][j].adjvex ] > road[now][j].cost)
                prim[ road[now][j].adjvex ]=road[now][j].cost;
    }
    return lowcost;
}

int main()
{
    int t,n,i,x,y,s;

    while(scanf("%d",&n)==1 && n!=0)
    {
        memset(road,0,sizeof(road));
        for(i=0;i<Max;i++)
        {   prim[i]=9999;v[i]=false;}
        t=n*(n-1)/2;
        for(i=0;i<t;i++)
        {
            scanf("%d %d %d",&x,&y,&s);
            road[x][0].adjvex++;
            road[x][ road[x][0].adjvex ].adjvex=y;
            road[x][ road[x][0].adjvex ].cost=s;
            road[y][0].adjvex++;
            road[y][ road[y][0].adjvex ].adjvex=x;
            road[y][ road[y][0].adjvex ].cost=s;
        }
        cout<<MST_Prim(n)<<endl;
    }
    return 0;
}