Highways POJ 1751（最小生成树）

http://acm.hust.edu.cn/vjudge/contest/121380#problem/G

题意：给出N个村庄的坐标，以及在这些村庄中哪些已经是连通的，让你求出在最小的花费下，让每个村庄都能直接或间接到达，输出需要彼此联通的村庄

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <queue>
using namespace std;

#define maxn 800
#define oo 0x3f3f3f3f
int maps[maxn][maxn], v[maxn], dist[maxn], num[maxn], n;
///num[]数组用来记录父节点


struct node
{
    int x, y;
}s[maxn], p[maxn];

void Init()
{
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(i == j)
                maps[i][j] = 0;
            else
                maps[i][j] = maps[j][i] = oo;
        }
    }
}

void Dij()
{
    memset(v, 0, sizeof(v));
    int k = 1;

    for(int i=1; i<=n; i++)
    {
         dist[i] = maps[1][i];
         num[i] = k;
    }

        v[1] = 1;

    for(int i=1; i<n; i++)
    {

        int mins = oo;
        int index = -1;

        for(int j=1; j<=n; j++)
        {
            if(!v[j] && dist[j]<mins)
            {
                index = j;
                mins = dist[j];
            }
        }

       if(mins)
        printf("%d %d
", num[index], index);

       v[index] = 1;

       for(int j=1; j<=n; j++)
       {
           if(!v[j] && dist[j] > maps[index][j])
           {
                dist[j] = maps[index][j];
                num[j] = index;
           }

       }
    }
}


int main()
{
    int  m;

    scanf("%d", &n);

    for(int i=1; i<=n; i++)
        scanf("%d %d", &s[i].x, &s[i].y);

        Init();

    for(int i=1; i<n; i++)
    {
        for(int j=i+1; j<=n; j++)
        {
            int l = (s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y);
            maps[i][j] = maps[j][i] = min(maps[i][j], l);
        }
    }

    scanf("%d", &m);
    int a, b;

    for(int i=1; i<=m; i++)
    {
        scanf("%d %d", &a, &b);
        maps[a][b] = maps[b][a] = 0;
    }


    Dij();


    return 0;
}