poj 3625 (最小生成树算法)
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 12203 | Accepted: 3448 |
Description
Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.
Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (Xi, Yi) on the plane (0 ≤ Xi ≤ 1,000,000; 0 ≤ Yi ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Two space-separated integers: Xi and Yi
* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.
Output
* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.
Sample Input
4 1
1 1
3 1
2 3
4 3
1 4
Sample Output
4.00
#include<iostream>
#include<stdio.h>
#include<cmath>
#define MAX_V 1005
using namespace std;
double cost[MAX_V][MAX_V];
double mincost[MAX_V];
bool used[MAX_V];
double X[MAX_V];double Y[MAX_V];
int V;
double min(double d1,double d2)
{
return d1<d2?d1:d2;
}
double prim()
{
for(int i=0;i<V;++i)
{
mincost[i]=1000000000.0;
used[i]=false;
}
mincost[0]=0;
double res=0;
while(true)
{
int v=-1;
for(int u=0;u<V;u++)
{
if(!used[u]&&(v==-1||mincost[u]<mincost[v]))v=u;
}
if(v==-1)break;
used[v]=true;
res+=mincost[v];
for(int u=0;u<V;u++)
{
mincost[u]=min(mincost[u],cost[v][u]);
}
}
return res;
}
double dis(int i,int j)
{
return sqrt((X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j]));
}
int main()
{
freopen("in.txt","r",stdin);
int M;
cin>>V>>M;
for(int i=0;i<V;i++)
{
cin>>X[i]>>Y[i];
}
for(int i=0;i<V;i++)
{
for(int j=i+1;j<V;j++)
{
cost[i][j]=cost[j][i]=dis(i,j);
}
}
for(int i=0;i<V;i++)cost[i][i]=1000000000.0;
int temp1,temp2;
while(M--)
{
cin>>temp1>>temp2;
//已经修建好的路则应理解为花费cost值为0
cost[temp1-1][temp2-1]=cost[temp2-1][temp1-1]=0;
}
double ans=prim();
printf("%.2f\n",ans);
return 0;
}
最新文章
- 论C#未来发展
- Java NIO原理分析
- WebForm中<;%=%>;与<;%#%>;的区别?
- 被IP代理网站屏蔽了,真是跪了
- How Tomcat Works(八)
- 根据中国气象局提供的API接口实现天气查询
- typdef struct 语法
- mongodb权威指南读书笔记
- 得到当前网址的域名 ASP.NET
- Angular学习笔记(一)
- springMVC学习总结(二)路径映射和请求方法限定
- Python内置函数(57)——print
- Flask入门之Bootstrap介绍使用和Flask-Nav快速导航栏
- 286万QPS!腾讯云TDSQL打造数据库领域的“超音速战机”
- hdu 4542 ";小明系列故事——未知剩余系"; (反素数+DFS剪枝)
- ConcurrentHashMap源码理解
- 我的集合学习笔记--ArrayList
- 黄聪:iOS $299刀企业证书申请的过程以及细节补充
- nginx命令启动及选项
- 基于webview的Hybrid app和React Native及html5