Posted on 2010-10-02 22:24
成幸毅 阅读(244)
评论(0) 编辑 收藏 引用
kruscal，水过。
官方做法是用dijkstra把松弛操作改成 d[j] = d[j]<min(d[i],graph[i][j])?min(d[i],graph[i][j]):d[j]; 其中d[i]代表的就是求从1到i路径中最小边的最大值。
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 10001;
struct node 
{
int u,v,w;
bool operator < (node a) const {
return w > a.w;
}
}edge[MAXN*MAXN+10];
int x,y,z;
int n,m;
int father[MAXN],rank[MAXN];
int _find(int x) {
int h = x;
while(father[h] != h)
h = father[h];;
int i = x;
while(i != h) {
int j = father[i];
father[i] = h;
i = j;
}
return h;
}
void _union(int a,int b) {
int p = _find(a);
int q = _find(b);
if(p == q) return;
if(rank[p] > rank[q]) {
father[q] = p;
return ;
}
else if(rank[p] == rank[q])
rank[q]++;
father[p] = q;
return ;
}
void make() {
for(int i = 0; i <= n; i++) {
father[i] = i;
rank[i] = 0;
}
}
int main() {
int cas;
scanf("%d",&cas);
for(int c = 1; c <= cas; c++) {
scanf("%d%d",&n,&m);
make();
for(int i = 0; i < m; i++) {
scanf("%d%d%d",&x,&y,&z);
edge[i].u = x;
edge[i].v = y;
edge[i].w = z;
}
sort(edge,edge+m);
for(int j = 0; j < m ;j++) {
int a = _find(edge[j].u);
int b = _find(edge[j].v);
if(a!=b) {
_union(edge[j].u,edge[j].v);
}
int r1 = _find(1);
int r2 = _find(n);
if(r1 == r2) {
printf("Scenario #%d:\n",c);
printf("%d\n",edge[j].w);
printf("\n");
break;
}
}
}
// system("pause");
return 0;
}