P1396 营救

题目链接：https://www.luogu.com.cn/problem/P1396

法一：二分+并查集

题目求经过道路的拥挤度最大值最小。我们可以考虑二分。我们就分距离。

L = （边的最小值） R = （边的最大值）

于是我们可以得到

while(l <= r)
{
    mid = (l +r) >> 1;
    if(check(mid)) ans = mid,r = mid - 1;
    else l = mid + 1;
}

现在的问题就是check函数怎么写

我们可以这样写：如果用权值小于等于mid的边能到达t，return 1;

else return 0;

看到有人在check里跑最短路，但是蒟蒻觉得不用，只有将权值小于等于mid的边的量个点合并起来，最后再用并查集判一下

bool check(int x)
{
    for(register int i = 1;i <= n; i++) fa[i] = i;
    for(int i = 1;i <= m; i++) if(val[i] <= x) H_(u[i],go[i]);
    //合并
    return judge(a,b);
   //用并查集判一下
}

【代码】

#include<bits/stdc++.h>
//#define min(x,y)(x<y?x:y)
//#define max(x,y)(x>y?x:y)
using namespace std;
int n,m,u[20005],v[20005],w[20005];
int f[10005],s,t;
int l=999999999,r,mid,ans;

int add(int n){
    if(f[n]==n) return n;
    return f[n]=add(f[n]);
}
//并查集
 
void hb(int x,int y){
    if(add(x)!=add(y))  f[add(x)]=f[add(y)];
}
//合并
 
bool pd(int a,int b){
    if(add(a)!=add(b)) return 0;
    else return 1;
}
//判断两点是否连通 
 
bool check(int x){
    for(int i=1;i<=n;i++){
        f[i]=i;
    }
    for(int i=1;i<=m;i++) if(w[i]<=x) hb(u[i],v[i]);
    return pd(s,t);
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        cin>>u[i]>>v[i]>>w[i];
        l=min(l,w[i]),r=max(r,w[i]);
    }
//    cout<<"l:"<<l<<" "<<"r:"<<r<<endl;
    
    while(l<=r){
        mid=(l+r)>>1;
//        cout<<"mid:"<<mid<<endl;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans<<endl;
    return 0;
}

法二：克鲁斯卡尔

将边从小到大排序,然后克鲁斯卡尔最小生成树连边,这样当S和T第一次联通时,当前边的权值就是答案了.

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,ans;
int f[10005];

struct node{
    int u,v,w;
}b[20005];

int add(int n){
    if(f[n]==0) return n;
    return f[n]=add(f[n]); 
}

bool cmp(node x,node y){
    return x.w<y.w;
}

int main(){
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++){
        cin>>b[i].u>>b[i].v>>b[i].w;
    }
    sort(b+1,b+m+1,cmp);
    for(int i=1;i<=m;i++){
        int xx=add(b[i].u) , yy=add(b[i].v);
        if(xx!=yy){
            f[xx]=yy;
        }
        if(add(s)==add(t)){
            cout<<b[i].w<<endl;
            return 0;
        }
    }
    return 0;
}