HDU 1102 Constructing Roads

赤裸裸的最小生成树。

题目大意就是输入一个N表示有n个村庄，然后输入n行n列，第i行j个元素表示i村庄离j村庄的路数多远（所以i行i列一般为零），然后输入q，表示q条路已修，然后输入q对数就可以了。（权值为零）。求使其n个村庄最小的连通值。

需要注意的是可能会有重复的路出现，但是有不同的值。既然是求最小生成树，那么可以用prim算法在输入路的时候保证是最小的值。

代码如下

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int map[105][105];
int vis[105];
int prim(int n)
{
    int pos,i,j,d[105],ans,min;
    memset(vis,0,sizeof(vis));
    ans = 0;

    for(i = 2;i <= n;i++)
    d[i] = map[1][i];

    vis[1] = 1;
    for(i = 1;i < n;i++)//次数很重要
    {
        min = 0x7fffffff;
        for(j = 2;j <= n;j++)//是1是2无所谓，因为不会差1
        {
            if(!vis[j] && min > d[j])
            min = d[j],pos = j;
        }
        ans += min;
        vis[pos] = 1;

        for(j = 2;j <= n;j++)
        if(!vis[j] && map[pos][j] < d[j])//切记这里的判断大小的方向
        d[j] = map[pos][j];
    }
    return ans;
}
int main()
{
    int n,i,j,a,q,b,c,ans;
    while(~scanf("%d",&n))
    {
        ans = 0;
        for(i = 1;i <= n;i++)
            for(j =1;j <= n;j++)
            map[i][j] = 0x7fffffff;

        for(i = 1;i <= n;i++)
        {
            for(j =1;j <= n;j++)
            {
                scanf("%d",&a);
                if(map[i][j] > a || map[j][i] > a)
                map[i][j] = map[j][i] = a;
            }
        }
        scanf("%d",&q);
        while(q--)
        {
            scanf("%d %d",&b,&c);
            map[b][c] = map[c][b] = 0;
        }

        ans = prim(n);
        printf("%d\n",ans);

    }
    return 0;
}