POJ 1751 Highways

題意：n個城市，然后把n個城市的坐標都給你，然后給你m條已經修好的道路，然后給出m個已經修好道路的城市a，b，

However, they want to guarantee that every town is highway-reachable from every other town.

他們保證任何城市都是可以通過其他城市到達的

很明顯是個最小生成樹問題、

最后讓你輸出所有需要另外加的道路連接的兩個城市a b、

思路：先對所有n個城市求一遍距離、然后對已經修好道路的城市賦值為0、輸出的時候要使用一下前驅數組（用來記錄一個點的前驅是哪一個點）

?

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int qq=800;
const int MAX=1e8;
int n,m,sum;
int map[qq][qq];
int cost[qq+300];
int vis[qq];
int pre[qq];
int x[qq],y[qq];
void prim()
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;++i){
        cost[i]=map[1][i];
        pre[i]=1;            //初始化前驅、因為剛開始加的1,所以將每一個點的前驅設置為1 
    }        
    vis[1]=1;
    int minx,k;
    for(int i=1;i<=n;++i){
        minx=MAX;
        for(int j=1;j<=n;++j)
            if(!vis[j] && cost[j]<minx)
                minx=cost[k=j];
        if(map[pre[k]][k])    printf("%d %d\n",pre[k],k);    //當道路不存在時，輸出前驅、 
        vis[k]=1;
        for(int j=1;j<=n;++j)
            if(map[k][j]<cost[j]){
                cost[j]=map[k][j];
                pre[j]=k;        //更新前驅、 
            }    
    }
}
int main()
{
    scanf("%d",&n);
    int i,j,a,b;
    for(i=1;i<=n;++i){
        scanf("%d%d",&x[i],&y[i]);
        for(j=1;j<i;++j){
            if(i==j)    map[i][j]=MAX;
            else        map[i][j]=map[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
        }
    }
    scanf("%d",&m);
    for(i=1;i<=m;++i){
        scanf("%d%d",&a,&b);
        map[a][b]=map[b][a]=0;
    }
    prim();    
    return 0;
}

?

，