[luogu] P1396 营救 二分答案+并查集

前言

二分答案 可真难啊。。 传送门 :

思路

我们可以通过边权的最大值和最小值进行二分答案

然后对于每一个答案 我们都通过并查集判断是否可以到达

CODE

#include 
using namespace std;
#define ll long long
#define endl '\n'
const int N  = 1e5+10;
const int INF = 0x3f3f3f3f3f;
int n,m,s,t,ans;
int a[N],b[N],vis[N],f[N];
int l = INF,r;
int find(int x)
{
    if(f[x]!=x)
    return f[x] = find(f[x]);
    return f[x];
}

inline void join(int a,int b)
{
    int fa = find(a),fb = find(b);
    if(fa!=fb)
    f[fa] =  fb;
}


inline bool check(int x)
{
    for(int i=1;i>m>>s>>t;
    for(int i=1;i>a[i]>>b[i]>>vis[i],l = min(l,vis[i]),r=max(r,vis[i]);

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