链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1338
题目:
Problem E
Connect the Campus
Input:standard input
Output:standard output
Time Limit:2 seconds
Many new buildings are under construction on the campus of theUniversityofWaterloo. The university has hired bricklayers, electricians, plumbers, and a computer programmer. A computer programmer? Yes, you have been hired to ensure that each building is
connected to every other building (directly or indirectly) through the campus network of communication cables.
We will treat each building as a point specified by an x-coordinate and a y-coordinate. Each communication cable connects exactly two buildings, following a straight line between the buildings. Information travels along a cable in both directions. Cables
can freely cross each other, but they are only connected together at their endpoints (at buildings).
You have been given a campus map which shows the locations of all buildings and existing communication cables. You must not alter the existing cables. Determine where to install new communication cables so that all buildings are connected. Of course, the
university wants you to minimize the amount of new cable that you use.
Fig:UniversityofWaterlooCampus
Input
The input file describes several test case.The description of each test case is given below:
The first line of each test case contains the number of buildingsN (1<=N<=750). The buildings are labeled from1toN. The nextNlines give thexandycoordinates
of the buildings. These coordinates are integers with absolute values at most10000. No two buildings occupy the same point. After that there is a line containing the number of existing cablesM (0 <= M <= 1000)followed byMlines
describing the existing cables. Each cable is represented by two integers: the building numbers which are directly connected by the cable. There is at most one cable directly connecting each pair of buildings.
Output
For each set of input, output in a single line the total length of the new cables that you plan to use, rounded to two decimal places.
Sample Input
4
103 104
104 100
104 103
100 100
1
4 2
4
103 104
104 100
104 103
100 100
1
4 2
Sample Output
4.41
4.41
分析与总结:
最小生成树, 但是有点变化,有些边是已经建好的,那么把这些建好的边权值赋值为0,然后直接模板
代码:
1.Prim
#include<cstdio>
#include<cstring>
#include<cmath>
#define N 760
double w[N][N],x[N],y[N],key[N];
int pre[N], hash[N], n, m;
inline double getDist(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double Prim(){
memset(hash, 0, sizeof(hash));
hash[1] = 1;
for(int i=1; i<=n; ++i){
key[i] = w[1][i]; pre[i]=1;
}
double sum=0;
for(int i=1; i<n; ++i){
int u=-1;
for(int j=1; j<=n; ++j)if(!hash[j]){
if(u==-1||key[j]<key[u])
u=j;
}
sum += w[pre[u]][u];
hash[u] = 1;
for(int j=1; j<=n; ++j)if(!hash[j]){
if(key[j]>w[u][j]){
key[j] = w[u][j];
pre[j] = u;
}
}
}
return sum;
}
int main(){
int u,v;
while(~scanf("%d",&n)){
memset(w, 0, sizeof(w));
for(int i=1; i<=n; ++i)
scanf("%lf%lf",&x[i],&y[i]);
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)if(i!=j)
w[i][j] = getDist(x[i],y[i],x[j],y[j]);
scanf("%d",&m);
for(int i=0; i<m; ++i){
scanf("%d%d",&u,&v);
w[u][v]=w[v][u]=0;
}
printf("%.2f\n", Prim());
}
return 0;
}
2.Kruskal
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 760
using namespace std;
double w[N][N],x[N],y[N];
int f[N*N], rank[N*N], n, m;
struct Edge{
int u,v;
double val;
friend bool operator<(const Edge&a,const Edge&b){
return a.val < b.val;
}
}arr[N*N];
inline double getDist(double x1,double y1,double x2,double y2){
return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void init(){
for(int i=0; i<=n*n; ++i)
f[i]=i, rank[i]=0;
}
int find(int x){
int i, j=x;
while(j!=f[j]) j=f[j];
while(x!=j){
i=f[x]; f[x]=j; x=i;
}
return j;
}
bool Union(int x,int y){
int a=find(x),b=find(y);
if(a==b)return false;
if(rank[a]>rank[b])
f[b]=a;
else{
if(rank[a]==rank[b])
++rank[b];
f[a]=b;
}
return true;
}
int main(){
int u,v;
while(~scanf("%d",&n)){
memset(w, 0, sizeof(w));
for(int i=1; i<=n; ++i)
scanf("%lf%lf",&x[i],&y[i]);
for(int i=1; i<=n; ++i)
for(int j=1; j<=n; ++j)if(i!=j)
w[i][j] = getDist(x[i],y[i],x[j],y[j]);
scanf("%d",&m);
for(int i=0; i<m; ++i){
scanf("%d%d",&u,&v);
w[u][v]=w[v][u]=0;
}
int pos=0;
for(int i=1; i<=n; ++i)
for(int j=i+1; j<=n; ++j){
arr[pos].u=i,arr[pos].v=j;
arr[pos++].val = w[i][j];
}
init();
sort(arr,arr+pos);
double ans=0;
for(int i=0; i<pos; ++i){
if(Union(arr[i].u,arr[i].v))
ans += arr[i].val;
}
printf("%.2f\n", ans);
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于UVaOJ - 401. 水题。
开源项目-codingsince1985-UVa#uva-online-judge-solutions-in-golang.zip,两年来每天都在解决一个uva在线裁判问题,算起来…
uva705 Slash Maze 的代码,在UVaOJ上通过
PDF试题
uva532 Dungeon Master的源代码,并且AC了
Algorithm-UVA-Solutions-in-Python.zip,python 3中各种uva(acm)问题的解决方案。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
这是UVA133 TheDoleQueue救济金发放问题,经典的算法问题。初学算法的人要对这种算法非常熟悉并且能熟练运用。
tpcw-nyu-uva-client 客户端
leetcode 2 算法-Java UVa Online Judge(ACM-ICPC Live ...使用:数组、哈希表、链表、二分搜索、动态规划、堆栈、堆、reedy、排序、树 DFS、BFS、图、二分搜索树、递归、记忆、队列、映射等。...Uva-ACM-ICPC