Highways(POJ—2485)

简介: Highways(POJ—2485)

题目:

Flatopia岛国完全平坦。不幸的是,Flatopia的公共高速公路系统非常糟糕。弗拉托利亚政府意识到了这个问题,并且已经建造了一些连接一些最重要城镇的高速公路。但是,仍有一些城镇无法通过高速公路抵达。有必要建造更多的高速公路,以便能够在不离开高速公路系统的情况下在任何一对城镇之间行驶。

Flatopian城镇的编号从1到N,城镇i的位置由笛卡尔坐标(xi,yi)给出。每条高速公路连接两个城镇。所有高速公路(原始高速公路和要建造的高速公路)都遵循直线,因此它们的长度等于城镇之间的笛卡尔距离。所有高速公路都可以在两个方向使用。高速公路可以自由地相互交叉,但司机只能在位于两条高速公路尽头的小镇的高速公路之间切换。

Flatopian政府希望最大限度地降低建设新高速公路的成本。但是,他们希望保证每个城镇都可以从其他城镇到达公路。由于Flatopia是如此平坦,高速公路的成本总是与其长度成正比。因此,最便宜的高速公路系统将是最小化总公路长度的系统。

Input

输入包括两部分。第一部分描述了该国的所有城镇,第二部分描述了所有已建成的高速公路。

输入文件的第一行包含一个整数N(1 <= N <= 750),表示城镇数量。接下来的N行每行包含两个整数,xi和yi由空格分隔。这些值给出了第i个城镇的坐标(对于i从1到N)。坐标的绝对值不超过10000.每个城镇都有一个独特的位置。

下一行包含单个整数M(0 <= M <= 1000),表示现有高速公路的数量。接下来的M行每行包含一对由空格分隔的整数。这两个整数给出了一对已经通过高速公路连接的城镇号码。每对城镇至少由一条高速公路连接。

Output

为每条新高速公路写一条输出线,以便连接所有城镇,尽可能减少新高速公路的总长度。每条高速公路都应该通过打印这条高速公路连接的城镇号码来展示,并以空间隔开。

如果不需要建立新的高速公路(所有城镇都已连接),则应创建输出文件,但应该为空。

Sample Input

9
1 5
0 0 
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3
1 3
9 7
1 2

Sample Output

1 6
3 7
4 9
5 7
8 3

解题思路:给定n 个点的坐标,然后又给m个边表示该两个点已经连接起来不需要再建立高速公路。这个题考察的是Prim最短生成树算法,不过该题不是让我们求的是最短总距离,而是求出每一次所建立的边,既头结点和当前结点。

Code:

#include<stdio.h>
#include<string.h>
#include<math.h>
struct node
{
  int x;
  int y;  
}q[2000];
int e[2000][2000],book[5000],dis[50000],f[50000];//f[]是记录头结点的
int inf=999999999;
int count,sum;
int main()
{
  int i,j,k,min,n,m,b,t1,t2;
  while(scanf("%d",&n)!=EOF)
  {
    count=0;
    memset(book,0,sizeof(book));
    memset(dis,0,sizeof(dis));
    memset(f,0,sizeof(f));//数组清零
    for(i=1;i<=n;i++)
      scanf("%d%d",&q[i].x,&q[i].y);
    scanf("%d",&m);

    for(i=1;i<=n;i++)
      for(j=1;j<=n;j++)
        if(i==j)  e[i][j]=0;
        else        e[i][j]=inf;
    for(i=1;i<n;i++)
      for(j=i+1;j<=n;j++)
        e[i][j]=e[j][i]=((q[i].x-q[j].x)*(q[i].x-q[j].x)+(q[i].y-q[j].y)*(q[i].y-q[j].y));
    for(i=1;i<=m;i++)
    {
      scanf("%d%d",&t1,&t2);//已经建立的点就让两点之间距离的边为0
      e[t1][t2]=e[t2][t1]=0;
    }
    for(i=1;i<=n;i++)
      f[i]=1;//初始让所有头结点都为 1
    for(i=1;i<=n;i++)
      dis[i]=e[1][i];
    book[1]=1;
    count++;
    while(count<n)
    {
      min=inf;
      for(i=1;i<=n;i++)
      {
        if(book[i]==0&&dis[i]<min)
        {
          min=dis[i];
          j=i;
        }
      }
      book[j]=1;
      count++;
      if(e[f[j]][j]!=0)//输出要建立所要建立边的两点
        printf("%d %d\n",f[j],j);
      for(k=1;k<=n;k++)
      {
        if(book[k]==0&&dis[k]>e[j][k])
        {
          dis[k]=e[j][k];
          f[k]=j;//更新头结点
        } 
      }
    }   
  }
  return 0;
}

注意:题中的样例给出是随机的,也就是说求得的样例只要所对应的边一样就行了。

目录
打赏
0
0
0
0
63
分享
相关文章
POJ 1028
Web Navigation Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 23963   Accepted: 10692 Description Standard web bro...
782 0
poj 1751 Highways
点击打开链接poj 1751 思路:最小生成树+prime 分析:只要按照prime的思路求出所有的边,然后输出的时候判断是否是已经建好的即可。
767 0
POJ 2080(calender)
大致题意:给出自从2000 1 1过的天数,以-1结束,输出日期和星期 //以后遇到闰年的问题,坚决用二维数组 #include #include #define N 10010 char date[7][10]={"Sunday","Monday","Tuesday","Wedne...
798 0
POJ 2192
Zipper Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 13041   Accepted: 4560 Description Given three strings, you ...
743 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等