算法与数据结构Day02

修建道路

#include<stdio.h>
#include<string.h>
#include<algorithm>

using namespace std;
 
int inf=0x3f3f3f;
int map[105][105],dis[105],book[105];
int m,n;
 
int prim()
{
    int i,j,k,sum=0,u,min;
    
    for(i=1;i<=n;i++)
    {
        dis[i]=map[1][i];
        book[i]=0;
    }
    book[1]=1;
    for(i=1;i<n;i++)
    {
        min=inf;
        for(j=1;j<=n;j++)
        {
            if(book[j]==0&&min>dis[j])
            {
                min=dis[j];
                u=j;
            }
        }
        book[u]=1;
        sum+=dis[u];
        
        for(j=1;j<=n;j++)
        {
            if(book[j]==0&&dis[j]>map[u][j])
            dis[j]=map[u][j];
        }
    }
    return sum;
}
 
int main()
{
    int a,b,c,i,j,k;
    while(scanf("%d",&n)!=EOF)
    {
        memset(map,inf,sizeof(map));
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        scanf("%d",&a);
        for(i=1;i<=a;i++)
        {
            scanf("%d%d",&b,&c);
            map[b][c]=map[c][b]=0;
        }
        
        printf("%d\n",prim());
    }
    return 0;
}