1396

薛裕龙 · 2017-10-13 09:27:31 · 题解

这道题我一开始以为要用最短路。但仔细一看，如果用最短路疏松操作的话，最小的拥挤度很好求，但这是最大的拥挤度的最小值啊。如果你求出了每一个点的最小值，你怎么知道他是经过了哪些点到达的那个点呢，这就很是糊涂。于是我受到了最小生成树的启发，这其实也可以让权值从小到大依次连接各个点。每连接一次，就看看他的权值是否超过当前最大值，若超过就将值赋给它。

可能我的前面描述的不太清晰，上代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,m,s,t,maxx=-1;      maxx是代表最大的值
const int maxn=15000,maxm=35000;
struct zhu{              一直不知道我在干什么的人请kruskal算法练熟了
    int u,v,w;
}e[maxm];
int fa[maxn];     不知道这是干什么的好好学习并查集
int cmp(const zhu &a,const zhu &b)   
{
    return a.w<b.w;                                     
}
int find(int k)
{
    if(fa[k]==k)return k;
    else return fa[k]=find(fa[k]);         
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    }
    sort(e,e+m+1,cmp);
    for(int i=1;i<=n;i++)
    fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        int x=find(e[i].u);
        int y=find(e[i].v);
        if(x==y)continue;
        else{
            fa[x]=y;
            if(e[i].w>maxx)maxx=e[i].w;
            }    
        find(s);       注意这里必须查找两次，因为上面刚刚更新了 fa ，如果这里不刷新一次，s与t的fa可能有误
        find(t);
        if(fa[s]==t||fa[s]==fa[t]||s==fa[t])
        break;                                     之所以有着三个，是因为路是双向的，不一定fa刚好在t身上，所以有三种情况来退出
    }
    printf("%d",maxx);
    return 0;
}