Highways

poj1751:http://poj.org/problem?id=1751

题意：给你n个城市，每个城市的坐标给你，然后为了是每个城市都连通，需要在已经建了一些街道额基础上，再次建一些街道使其连通，求使得所建街道最短的那些边。
题解：直接求一棵生成树，把已经建好的边的边权设置为0，用prim走一遍。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #define INF 100000000.0

 using namespace std;

 struct Node{

     int x;

     int y;

 }node[];//储存村庄

 double g[][];

 double lowcost[];

 bool flag;

 double juli(Node a,Node b){//求距离 ，注意数据类型

     double xx=pow(((double)a.x-b.x),);

     double yy=pow(((double)a.y-b.y),);

     return sqrt(xx+yy);

 }

 int n,m,nearvex[],u,v1;

 void prim(int v0){

     flag=false;//标记是否需要建边

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

         lowcost[i]=g[v0][i];

         nearvex[i]=v0;

     }

     nearvex[v0]=-;

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

         double min=INF;//注意这里的数据类型，不能换成int

         int v=-;

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

             if(nearvex[j]!=-&&lowcost[j]<min){

                 v=j;

                 min=lowcost[j];

             }

         }

         if(v!=-){

             if(lowcost[v]!=){

                 flag=true;

                 printf("%d %d\n",nearvex[v],v);//找到就输出

             }

             nearvex[v]=-;

             for(int k=;k<=n;k++){

                 if(nearvex[k]!=-&&g[v][k]<lowcost[k]){

                     nearvex[k]=v;

                     lowcost[k]=g[v][k];

                 }

             }

         }

     }

   if(!flag)printf("\n");//没有要建的边，就输出空行

 }

 int main(){

     while(~scanf("%d",&n)){

        for(int i=;i<=n;i++)//存点

           scanf("%d%d",&node[i].x,&node[i].y);

        for(int i=;i<=n;i++)//建图

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

               g[i][j]=g[j][i]=juli(node[i],node[j]);

           }

         for(int i=;i<=n;i++)//初始化

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

              if(i==j)g[i][j]=;

              else if(g[i][j]==)g[i][j]=INF;

          }

         scanf("%d",&m);

         for(int i=;i<=m;i++){//处理已经不需要建的边

             scanf("%d%d",&u,&v1);

             g[u][v1]=g[v1][u]=;

         }

         prim();

     }

 }