tx1102.cpp

杭州电子科技大学在线系统ACM的1102题

#include<iostream>
#define N 101

int known[N];//记录点是否已被纳入最小生成树中
int dist[N];//记录当前灰色点的到黑色点的距离
int adj[N][N];//邻接矩阵
int n,q;

void Init()//初始化
{
    int x,y;
    memset(known,0,sizeof(known));//把所有点均设为未知
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",*(adj+i)+j);
    scanf("%d",&q);
    for(i=0;i<q;i++)
    {
        scanf("%d%d",&x,&y);
        adj[x-1][y-1]=adj[y-1][x-1]=0;//把原有的路赋权为0为下面程序提供方便
    }
    known[0]=1;
    for(i=0;i<n;i++)
        dist[i]=adj[0][i];//以0点开始找边过程，所以所有与0相接的点都成了灰色点
}

int Prim()
{
    int min,mini;
    int sum=0;
    while(1)
    {
        min=INT_MAX;//初始化最小值
        for(int i=0;i<n;i++)
            if(!known[i])//在未知点中找到一个权最小的点
                min=min>dist[i]?(mini=i,dist[i]):min;
        if(min==INT_MAX)
            break;
        sum+=min;
        known[mini]=1;//最小点的下标为mini
        for(int j=0;j<n;j++)
            dist[j]=dist[j]>adj[mini][j]?adj[mini][j]:dist[j];//更新灰色点
    }
    return sum;
}

int main()
{
    int res;
    while(scanf("%d",&n)!=EOF)
    {
        Init();
        res=Prim();
        printf("%d\n",res);
    }
    return 0;
}