//UVA 10048 - Audiophobia
/*
题意:n个点,m条无向路,每条路有一个噪音指数,从两点间的路径中选一条路,使这条路的最大噪音指数最小
思路:排序+并查集 类似克鲁斯卡尔
*/
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
using namespace std;
#define N 105
int map[N][N];
int c,s,q;
int bin[N];
struct node{
int a;
int b;
int c;
}edge[N*N];
int cmp(const void *x,const void *y){
return (*(node *)x).c - (*(node *)y).c;
}
void init(){
int i;
for(i = 0; i < N; ++i)
bin[i] = i;
}
int find(int x){
int i,j,r=x;
while(r!=bin[r]){
r = bin[r];
}
i=x;
while(i!=r){
j=bin[i];
bin[i]=r;
i=j;
}
return r;
}
void merge(int x,int y){
int fx,fy;
fx=find(x);
fy=find(y);
if(fx<fy)
bin[fy]=fx;
else
bin[fx]=fy;
}
int main(){
int i,j,ca = 1;
int a,b;
while(scanf("%d %d %d",&c,&s,&q)!=EOF){
if(c == 0 && s == 0 && q ==0)
break;
for(i = 1; i <= s; ++i){
scanf("%d %d %d",&edge[i].a,&edge[i].b,&edge[i].c);
}
qsort(edge+1,s,sizeof(edge[0]),cmp);
if(ca != 1)
printf("\n");
printf("Case #%d\n",ca++);
for(i = 1; i <= q; ++i){
scanf("%d %d",&a,&b);
init();
for(j = 1; j <= s; ++j){
merge(edge[j].a,edge[j].b);
if(find(a) == find(b))
break;
}
if(j > s)
printf("no path\n");
else
printf("%d\n",edge[j].c);
}
}
return 0;
}
分享到:
相关推荐
uva272
UVA109的题解,经测试完全正确,还附有题解。
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
uva最全ac代码
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
c++的算法题四分树的实现-uva10771
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
UVA 题目,不是很难,试试吧
uva357的栈实现版本
uva10755 ac 代码,可以随意更改下载
《算法竞赛入门经典》UVa配套题目pdf版完整
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
uva_trilearn2002 源代码
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
主要是uvaoj习题相关题目 练习题目
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
UVA【UVA1267】Network拓展题:咖啡店数据 内含标程以及数据生成器