题解 P1396 【营救】

Hank · 2016-10-30 15:09:44 · 题解

最小生成树，排序后从小到大枚举边 再从边中找最大值

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,s,t;
struct heheda
{
    int x,y,z;
}a[20005];
int fa[10005]; //并查集 
int getint()//读入优化 
{
    int str=0;
    char ch;
    for(ch=getchar();ch<'0' || ch>'9' ; ch=getchar());
    for(;ch>='0' && ch<='9';ch=getchar())str=10*str+ch-'0';
    return str;
}
bool comp(const heheda &a,const heheda &b)
{
    return a.z<b.z;
}
int find(int x)
{
    int pre=x;
    while(fa[x]!=x)x=fa[x];//找爸爸 
    while(fa[pre]!=pre)//路径压缩 
    {
        fa[pre]=x;
        pre=fa[pre];
    }
    return x;
}
int main()
{
    int x,y,z;
    n=getint();
    m=getint();
    s=getint();
    t=getint();
    for(int i=1;i<=m;i++)
    {
        a[i].x=getint();
        a[i].y=getint();
        a[i].z=getint();
    }
    for(int i=1;i<=n;i++)fa[i]=i;//初始化 
    sort(a+1,a+m+1,comp);//排序 
    int k=0;
    int ans=0;
    for(int i=1;i<=m;i++)
    {
        int x1=find(a[i].x);int x2=find(a[i].y);
        ans=max(ans,a[i].z);
        if(x1==x2)continue;//若已经连起来了 就继续 
        fa[x2]=x1;//连接 
        k++;
        if(k==n-1)
        break;
        if(find(s)==find(t))break;//s、t相连 退出 
    }
    printf("%d",ans);
}