点击打开链接uva 10397
题目意思:给定n个点,要求找到链接n个点最小路径长度
思路:Prime + 最小生成树
分析: 简单的最小生成树题目,直接套上模板即可
代码:
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
#define MAXN 1010
#define INF 0xFFFFFFF
int n , m;
double ans;
double G[MAXN][MAXN];
int vis[MAXN];
double lowcost[MAXN];
struct Point{
double x;
double y;
}p[MAXN];
void init(){
for(int i = 1 ; i <= n ;i++){
for(int j = 1 ; j <= n ; j++){
double tmp_x , tmp_y;
tmp_x = (p[i].x-p[j].x)*(p[i].x-p[j].x);
tmp_y = (p[i].y-p[j].y)*(p[i].y-p[j].y);
G[i][j] = sqrt(tmp_x + tmp_y);
}
}
}
void Prime(){
int pos;
double min;
ans = 0;
memset(vis , 0 , sizeof(vis));
vis[1] = 1;
for(int i = 1 ; i <= n ; i++)
lowcost[i] = G[1][i];
for(int i = 1 ; i <= n ; i++){
min = INF;
for(int j = 1 ; j <= n ; j++){
if(!vis[j] && lowcost[j] < min){
min = lowcost[j];
pos = j;
}
}
if(min == INF)
break;
ans += min;
vis[pos] = 1;
for(int j = 1 ; j <= n ; j++){
if(!vis[j] && lowcost[j] > G[pos][j])
lowcost[j] = G[pos][j];
}
}
printf("%.2lf\n" , ans);
}
int main(){
int a , b;
while(scanf("%d" , &n) != EOF){
for(int i = 1 ; i <= n ; i++)
scanf("%lf%lf" , &p[i].x , &p[i].y);
init();
scanf("%d" , &m);
for(int i = 0 ; i < m ; i++){
scanf("%d%d" , &a , &b);
G[a][b] = G[b][a] = 0;
}
Prime();
}
}
分享到:
相关推荐
判断输入字符串是否为镜像或回文串。 来源于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