POJ1751 Highways

题目链接 http://poj.org/problem?id=1751

题目大意：输入n；然后给你n个点的坐标（任意两点之间皆可达）；输入m；接下来m行每行输入两个整数x，y表示点x与点y 已经相连；

问连接所有点至少还需要连接哪些点（并且使连接后总距离最短），并输出连接的点对。

思路：最小生成树，用prim或者kruskal，我是用prim写的，

　　　所以处理已连接的m个点对时，只需将两个点之间的距离设为0即可，这样进行算法时，

　　　会优先处理已连接的点。然后输出点对时，判断下d[i]是否为0，若为0，则是已经连接过的点，否则输出

　　AC代码：

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <queue>

#include <string>

#include <vector>

#include <set>

#include <map>

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define fi first

#define se second

using namespace std;

#define gamma 0.5772156649015328606065120

#define MOD 1000000007

#define inf 0x3f3f3f3f

#define N 800

typedef long long LL;

typedef pair<int,int> PII;

struct COORD

{

    int x,y;

} coord[N];

int n,pic[N][N],path[N],vis[N],d[N];

void prim()

{

    memset(vis,,sizeof(vis));

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

        d[i]=pic[][i];

    vis[]=;

    for(int j=; j<n; ++j)

    {

        int fm=inf,u;

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

            if(!vis[i]&&d[i]<fm)

                fm=d[u=i];

        vis[u]=;

        if(d[u])   //若d[u]==0则是题目中已连接的点，跳过

        {

            if(!path[u]) printf("%d %d\n",,u); //若path[u]==0则是与点1相连

            else printf("%d %d\n",path[u],u);

        }

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

            if(!vis[i]&&pic[u][i]<d[i])

            {

                path[i]=u;

                d[i]=pic[u][i];

            }

    }

}

int main()

{

    int dis,x,y,m;

    scanf("%d",&n);

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

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

        for(int j=i+; j<=n; ++j)

        {

            dis=(coord[i].x-coord[j].x)*(coord[i].x-coord[j].x)+(coord[i].y-coord[j].y)*(coord[i].y-coord[j].y);

            pic[i][j]=pic[j][i]=dis;

        }

    scanf("%d",&m);

    for(int i=; i<=m; ++i)

    {

        scanf("%d%d",&x,&y);

        pic[x][y]=pic[y][x]=;

    }

    memset(path,,sizeof(path));   //path数组记录点对

    prim();

    return ;

}

Prim

POJ1751 Highways