注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TsReaper的博客

一起来玩算法竞赛吧~

 
 
 
 
 

日志

 
 

[题解]公路修建  

2015-08-07 10:09:37|  分类: 题解 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
关键字:最小生成树。

Link&Limit


        [洛谷1265]  [codevs2603]
        时间限制:1000ms  空间限制:131072kb

Description


        某国有n个城市,它们互相之间没有公路相通,因此交通十分不便。为解决这一“行路难”的问题,政府决定修建公路。修建公路的任务由各城市共同完成。
        修建工程分若干轮完成。在每一轮中,每个城市选择一个与它最近的城市,申请修建通往该城市的公路。政府负责审批这些申请以决定是否同意修建。
        政府审批的规则如下:
        (1)如果两个或以上城市申请修建同一条公路,则让它们共同修建;
        (2)如果三个或以上的城市申请修建的公路成环。如下图,A申请修建公路AB,B申请修建公路BC,C申请修建公路CA。则政府将否决其中最短的一条公路的修建申请;
[题解]公路修建 - TsReaper - TsReaper的博客
        (3)其他情况的申请一律同意。
        一轮修建结束后,可能会有若干城市可以通过公路直接或间接相连。这些可以互相:连通的城市即组成“城市联盟”。在下一轮修建中,每个“城市联盟”将被看作一个城市,发挥一个城市的作用。
        当所有城市被组合成一个“城市联盟”时,修建工程也就完成了。
        你的任务是根据城市的分布和前面讲到的规则,计算出将要修建的公路总长度。

Input Format


        第一行一个整数n,表示城市的数量。(n≤5000)
        以下n行,每行两个整数x和y,表示一个城市的坐标。(-1000000≤x,y≤1000000)

Output Format


        一个实数,四舍五入保留两位小数,表示公路总长。(保证有惟一解)

Sample Input #1


4
0 0
1 2
-1 2
0 4

Sample Output #1


6.47

        可以证明规则2是不可能出现的:如果需要出现规则2,则有AB>BC>CA>AB矛盾。而城市联盟的组建过程,正是一个类似于用Prim求出最小生成树的过程。所以,我们直接用Prim求出整张图的最小生成树即可。另外,由于5000*5000的double数组可能超出内存限制,所以我们不必记录每一对城市间的距离,需要的时候直接计算即可。

#include <stdio.h>
#include <math.h>
int n;
long long x[5010],y[5010];
double dis[5010];
short vis[5010];
double min(double a,double b)
{
return a<b?a:b;
}
double prim()
{
int i,j,nxt;
double nxtdis,tans = 0;
for(i=2;i<=n;i++)
{
nxtdis = 999999999;
for(j=1;j<=n;j++)
{
if(vis[j]) continue;
if(nxtdis>dis[j]) { nxtdis = dis[j]; nxt = j;}
}
tans += nxtdis; vis[nxt] = 1;
for(j=1;j<=n;j++) dis[j] = min(dis[j],sqrt((x[nxt]-x[j])*(x[nxt]-x[j])+(y[nxt]-y[j])*(y[nxt]-y[j])));
}
return tans;
}
int main()
{
int i;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%lld%lld",&x[i],&y[i]);
for(i=1;i<=n;i++) dis[i] = sqrt((x[1]-x[i])*(x[1]-x[i])+(y[1]-y[i])*(y[1]-y[i]));
vis[1] = 1;
printf("%.2f",prim());
return 0;
}

  评论这张
 
阅读(18)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018