点击打开链接uva 10048
题目意思:
现在城市污染很严重,除了平常的污染外还有什么声音污染。现在有c个城市,s个街道,每一个街道有一个声音的分贝值。现在由于从某一点到另外一点有很多条路径,现在要求我们找到一条路径中使得这条路径上的最大的声音分贝是所有可达路径中最小的。如果没有输出“no path”,否则额输出这个最小值。
思路:最小生成树+kruskal
要求:所有满足能够到达终点的路径中一条边的最大值中的最小值,那么自然跟最小生成树联系起来
分析:利用kruskal的算法的思想,我们先把所有的要求的路径保存起来。那么利用kruskal开始生成树,每加入一个连通分量的我们就去判断所有要求的路径中是否已经在同一个连通分量里面并且没有求过,因为我们知道如果两个点在这一次合并后变成同一个连通分量,那么这两个点的最短路已经形成,并且由于kruskal的性质上一次加入的边长度肯定比下一次加入的小。所以可以知道这个路径要求的ans 就是当前的这个边的权值(具体好好想想,表达能力实在有限)。
代码:
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 110
int c , s , q , cnt;
int father[MAXN];
int rank[MAXN];
int ans[10010];
struct query{
int x;
int y;
}que[10010];
struct Edge{
int x;
int y;
int value;
}e[1010];
bool cmp(Edge e1 , Edge e2){
return e1.value < e2.value;
}
void init_Set(){
for(int i = 1 ; i <= c ; i++){
father[i] = i;
rank[i] = 1;
}
}
int find_Set(int x){
int tmp = x;
while(father[tmp] != tmp)
tmp = father[tmp];
while(father[x] != tmp){
int tmp_x = father[x];
father[x] = tmp;
x = tmp_x;
}
return tmp;
}
void union_Set(int x, int y){
if(rank[x] >= rank[y]){
rank[x] += rank[y];
father[y] = x;
}
else{
rank[y] += rank[x];
father[x] = y;
}
}
void judge(int x){
for(int i = 0 ; i < q ; i++){
if(find_Set(que[i].x) == find_Set(que[i].y) && !ans[i])
ans[i] = e[x].value;
}
}
void Kruskal(){
printf("Case #%d\n" , cnt++);
init_Set();
sort(e , e+s , cmp);
memset(ans , 0 , sizeof(ans));
for(int i = 0 ; i < s ; i++){
int root_x = find_Set(e[i].x);
int root_y = find_Set(e[i].y);
if(root_x != root_y){
union_Set(root_x , root_y);
judge(i);
}
}
for(int i = 0 ; i < q ; i++){
if(ans[i])
printf("%d\n" , ans[i]);
else
printf("no path\n");
}
}
int main(){
//freopen("input.txt" , "r" , stdin);
int flag = 1;
cnt = 1;
while(scanf("%d%d%d" , &c , &s , &q) && c+s+q){
for(int i = 0 ; i < s ; i++)
scanf("%d%d%d" , &e[i].x , &e[i].y , &e[i].value);
for(int i = 0 ; i < q ; i++)
scanf("%d%d" , &que[i].x , &que[i].y);
if(flag)
flag = 0;
else
printf("\n");
Kruskal();
}
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