Posted on 2010-10-02 22:24
成幸毅 阅读(248)
评论(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;
}
