POJ 2395 Out of Hay 草荒 (MST,Kruscal,最小瓶颈树)

题意:Bessie要从牧场1到达各大牧场去,他从不关心他要走多远,他只关心他的水袋够不够水,他可以在任意牧场补给水,问他走完各大牧场,最多的一次需要多少带多少单位的水?

思路:其实就是要让所带的水尽量少,即所选的每条路都要尽量短,即最小瓶颈生成树。其实也就是最小生成树。再求生成树上权值最大的边即可。

 //#include <bits/stdc++.h>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define INF 0x7f7f7f7f
#define pii pair<int,int>
#define LL long long
using namespace std;
const int N=; int seq[N], a[N], b[N], w[N], pre[N];
int cmp(int a,int b)
{
return w[a]<w[b];
} int find(int x)
{
return pre[x]==x? x: pre[x]=find(pre[x]);
} int cal(int n, int m)
{
int ans=;
for(int i=; i<=n; i++) pre[i]=i;
for(int i=; i<m; i++)
{
int u=find(a[seq[i]]);
int v=find(b[seq[i]]);
if( u!=v )
{
pre[u]=v; //不是同个连通块,则连接。
ans=max(ans, w[seq[i]]);
}
} return ans;
} int main()
{
freopen("input.txt", "r", stdin);
int t, n, m; while(cin>>n>>m)
{
for(int i=; i<m; i++)
{
seq[i]=i;
scanf("%d%d%d", &a[i], &b[i], &w[i]);
}
sort(seq,seq+m,cmp);
cout<<cal(n, m)<<endl;
}
return ;
}

AC代码

上一篇:javascript基础入门之js中的结构分支与循环语句


下一篇:Android权限安全(8)ContentProvider基于URI的安全