学步园

题意：给定N个城市的坐标，然后下面给出M个已经连接好的城市标号，求他们之间的最小生成树，其中，已连接的话，不必输出。

思路：将已给的城市之间距离标为0，输出的时候，城市之间为零的就不必输出。

#include<iostream><br /> #include<cstdio><br /> #include<cstring><br /> #include<math.h><br /> using namespace std;<br /> class tt<br /> {<br /> public:<br /> int x,y;<br /> }town[760];<br /> int g[760][760];<br /> int n,m;<br /> void solve_dis()<br /> {<br /> int i,j;<br /> for(i=1;i<n;i++)<br /> {<br /> for(j=i+1;j<=n;j++)<br /> {<br /> g[i][j]=g[j][i]=((town[i].x-town[j].x)*(town[i].x-town[j].x)+(town[i].y-town[j].y)*(town[i].y-town[j].y));<br /> }<br /> }<br /> }<br /> void prim()<br /> {<br /> int i,j,k,maxcost =999999999,min;<br /> int dist[760],pre[760];<br /> bool vis[760];<br /> memset(vis,true,sizeof(vis));<br /> for(i=1;i<=n;i++)<br /> {<br /> dist[i]=maxcost;<br /> pre[i]=1;<br /> }<br /> vis[1]=false;dist[1]=0;<br /> for(i=1;i<=n;i++)<br /> {<br /> min=maxcost;k=1;<br /> for(j=1;j<=n;j++)<br /> if(vis[j]&&dist[j]<min)<br /> { k=j; min=dist[j]; }<br /> vis[k]=false;<br /> for(j=1;j<=n;j++)<br /> if(dist[j]>g[k][j]&&vis[j])<br /> { dist[j]=g[k][j]; pre[j]=k;}<br /> }<br /> for(i=2;i<=n;i++)<br /> {<br /> if(g[pre[i]][i]!=0)<br /> {<br /> printf("%d %d/n",i,pre[i]);<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> int i,x,y;<br /> scanf("%d",&n);<br /> for(i=1;i<=n;i++)<br /> scanf("%d%d",&town[i].x,&town[i].y);<br /> solve_dis();<br /> scanf("%d",&m);<br /> for(i=0;i<m;i++)<br /> {<br /> scanf("%d%d",&x,&y);<br /> g[x][y]=g[y][x]=0;<br /> }<br /> prim();<br /> }<br />