二分与并查集应用

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,fa[10100],l=INT_MAX,r=INT_MIN,mid;
struct City{
	int x,y,len;
}a[20100];
int find(int x){
	if (fa[x]!=x)fa[x]=find(fa[x]);
	return fa[x];
}
void merge(int x,int y){
	int tx=find(x);
	int ty=find(y);
	if (tx!=ty)fa[tx]=ty;
}
bool check(int mid){
	for (int i=1;i<=n;i++)fa[i]=i;
	for (int i=1;i<=m;i++){
		if (a[i].len<=mid)merge(a[i].x,a[i].y);
	}
	return find(s)==find(t);
}
int main(){
	cin>>n>>m>>s>>t;
	for (int i=1;i<=m;i++){
		cin>>a[i].x>>a[i].y>>a[i].len;
		l=min(l,a[i].len);
		r=max(r,a[i].len);
	}
	while (l<=r){
		mid=l+r>>1;
		if (check(mid))r=mid-1;
		else l=mid+1;
	}
	cout<<l;
	return 0;
}

先对原图跑一遍最大生成树，建树，然后在最大生成树上倍增，找 $s → t$ 的最大边权。

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int u,v,w;
    bool operator<(const Node &b)const{
        return w<b.w;
    }
}p[20001];
struct Edge{
    int v,w;
};
int n,m,s,t,logn;
int fa[10001],de[10001];
int f[10001][20],mx[10001][20];
vector<Edge> e[10001];
int Find(int u){
    return u==fa[u]?u:fa[u]=Find(fa[u]);
}
void kruskal(){
    int cnt=0;
    for (int i=1;i<=m&&cnt<n-1;i++){
        int fu=Find(p[i].u),fv=Find(p[i].v);
        if (fu!=fv){
            fa[fv]=fu;
            e[p[i].u].push_back({p[i].v,p[i].w});
            e[p[i].v].push_back({p[i].u,p[i].w});
            cnt++;
        }
    }
}
void dfs(int u){
    for (int i=0;i<e[u].size();i++){
        int v=e[u][i].v;
        if (v==f[u][0]){
            continue;
        }
        int w=e[u][i].w;
        de[v]=de[u]+1;
        f[v][0]=u;
        mx[v][0]=w;
        dfs(v);
    }
}
int lca(){
    int maxx=0;
    if (de[s]<de[t]){
        swap(s,t);
    }
    for (int i=0,p=de[s]-de[t];p;i++,p>>=1){
        if (p&1){
            maxx=max(maxx,mx[s][i]);
            s=f[s][i];
        }
    }
    if (s==t){
        return maxx;
    }
    for (int i=logn;i>=0;i--){
        if (f[s][i]!=f[t][i]){
            maxx=max(maxx,mx[s][i]);
            s=f[s][i];
            maxx=max(maxx,mx[t][i]);
            t=f[t][i];
        }
    }
    return max(maxx,max(mx[s][0],mx[t][0]));
}
int main(){
    cin>>n>>m>>s>>t;
    for (int i=1;i<=n;i++){
        fa[i]=i;
    }
    for (int i=1;i<=m;i++){
        cin>>p[i].u>>p[i].v>>p[i].w;
    }
    sort(p+1,p+m+1);
    kruskal();
    dfs(1);
    logn=log2(n);
    for (int j=1;j<=logn;j++){
        for (int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
            mx[i][j]=max(mx[i][j-1],mx[f[i][j-1]][j-1]);
        }
    }
    cout<<lca();
    return 0;
}

话说为什么其他大佬们用的全是二分啊

方法1：
#include<bits/stdc++.h>
using namespace std;
int a[10001];
int n,m,s,t;
struct Road
{
	int u,v,w;
}x[20001];
bool cmp(Road i,Road j)
{
	return i.w<j.w;
}
void init()
{
	for(int i=1;i<=n;i++)
		a[i] = i;
}
int find(int k)
{
	if(a[k]==k)
		return k;
	else
		return a[k]=find(a[k]);
		
}
bool check(int mid)
{
	init();
	
	for(int i=1;i<=n&&x[i].w<=mid;i++)
	{
		if(find(x[i].u!=x[i].v))
			a[find(x[i].u)] = find(x[i].v);
	}
	
	return find(s)==find(t);
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&s,&t);
	
	
	int i;
	for(i=1;i<=m;i++)
		scanf("%d%d%d",&x[i].u,&x[i].v,&x[i].w);
	
	sort(x+1,x+1+m,cmp);

	int low,high,mid;
	low=x[1].w,high=x[m].w;

	while(low+1<high)
	{
		mid = (low+high)/2;
		if(check(mid))
			high = mid;
		else
			low = mid;
	}
	
	if(check(low))
		printf("%d",low);
	else
		printf("%d",high);

	return 0;
}
方法2：
#include<bits/stdc++.h>
using namespace std;
int m,n,s,t,l=INT_MAX,r=INT_MIN,mid,u[20015],v[20015],w[20015],ans;
int fa[20015];
int find(int x)
{
	if(fa[x]==x) return x;
	else return fa[x]=find(fa[x]);
}
void un(int x,int y)
{   int  fx=find(x);
	int  fy=find(y);
	if(fx!=fy)
	{
		fa[fx]=fy;
	}
}
bool check(int x)
{
	for(int i=1;i<=n;i++) fa[i]=i;	
	for(int i=1;i<=m;i++)
	{
		if(w[i]<=mid)
		{
			un(u[i],v[i]);
		}
		else continue;
	}
	if(find(fa[s])==find(fa[t])) return true;
	else return false;
}
int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&u[i],&v[i],&w[i]);
		l=min(l,w[i]);
		r=max(r,w[i]);
	}
	while(l<=r)
	{
		mid=(l+r)>>1;
		if(check(mid))
		{
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	cout<<ans;
}
方法3：
#include<bits/stdc++.h>
using namespace std;

int l=INT_MAX,r=INT_MIN,n,m,s,t,ans;
//cost:记录拥挤度 
int f[20010],x[20010],y[20010],cost[20010];

//查找
int find(int x){
	return x == f[x]?x:f[x]=find(f[x]);
} 

//二分函数，看拥挤度在mid的情况下从s到t是否有通路
bool check(int mid){
	for(int i = 1;i <= n;i++) f[i] = i;//初始化
	//m条路 
	for(int i = 1;i <= m;i++){
		//代价大于mid的通路无效 
		if(cost[i] > mid) continue;
		int fx = find(x[i]),fy = find(y[i]);
		//将x[i]和y[i]合并到同一个集合 
		if(fx != fy){
			f[fx] = fy;	
		} 
	} 
	
	//如果s到t有通路
	if(find(s) == find(t)) return true;
	else return false;
} 

int main(){
	cin>>n>>m>>s>>t;
	//读入m条路的拥挤度
	for(int i = 1;i <= m;i++){
		cin>>x[i]>>y[i]>>cost[i];
		l = min(l,cost[i]);
		r = max(r,cost[i]);
	} 
	
	//二分拥挤度，找左边界 
	int mid; 
	while(l <= r){
		mid = (l + r) >> 1;
		//如果在拥挤度为mid的情况下有通路，尝试降低mid 
		if(check(mid)){
			r = mid - 1;
		}else{
			l = mid + 1;
		}
	} 
	
	//输出左边界 
	cout<<l;
	return 0;
} 

#include <bits/stdc++.h>
using namespace std;
int l=INT_MAX,r=INT_MIN,n,m,s,t,ans;
int f[20010],x[20010],y[20010],cost[20010];
int find(int x)
{
	return x == f[x]?x:f[x]=find(f[x]);
} 
bool check(int mid)
{
	for(int i = 1;i <= n;i++) f[i] = i;
	for(int i = 1;i <= m;i++)
    {
		if(cost[i] > mid) continue;
		int fx = find(x[i]),fy = find(y[i]);
		if(fx != fy)
        {
			f[fx] = fy;	
		} 
	} 
	if(find(s) == find(t)) return true;
	else return false;
} 

int main()
{
	cin>>n>>m>>s>>t;
	for(int i = 1;i <= m;i++)
    {
		cin>>x[i]>>y[i]>>cost[i];
		l = min(l,cost[i]);
		r = max(r,cost[i]);
	} 
	int mid; 
	while(l <= r)
    {
		mid = (l + r) >> 1;
		if(check(mid))
        {
			r = mid - 1;
		}
        else
        {
			l = mid + 1;
		}
	} 
	cout<<l;
	return 0;
}//已AC