美丽的路径并查集，搜索，二分

本文主要是介绍美丽的路径并查集，搜索，二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：https://ac.nowcoder.com/acm/contest/9985/A

知识点：

并查集，搜索，二分

思路：
第 $\frac{k}{2}+1$ 小的数，那就是中位数，需要注意的是题目中没有说要是最短路，所以为了让美丽值最大，可以让这条路径在两个权值大的点之间反复行走。

那么可以发现会有很多个美丽值，那么可以对答案进行二分，去找最大的那个。

首先是判断起点到终点之间是否联通，这个用搜索，或者并查集都可以。

当可以连通的时候，二分。设当前美丽值为x，路径的美丽值就是此路径上的所有点的点权中第⌊k/2+1⌋小的点权，等价于大于等于x的点的数量大于等于路径中所有点的一半。

换句话说，如果发现大于等于x的点的数量大于等于路径中所有点的一半，说明此时的x值取小了， $l = m + 1$ ，否则 $r = m - 1$ .

如何判断大于等于x的点的数量大于等于路径中所有点数量的一半？

设大于等于x的点为1点，否则为0点。

当有两个1点连续时，可以不断来回走，必然大于一半。

只有当10101010交错出现时，且1的个数大于0的个数，必然大于一半。

容易发现只有0101010交错出现时，且开始点和结束点都为0，才会小于。

代码：

#include <bits/stdc++.h>
#include <iostream>
using namespace std;
const int maxn = 200005;
typedef long long ll;int a[maxn];
int vis[maxn];
int fa[maxn];vector<int> g[maxn];
int T,n,m,s,t;
int ans =0;
bool flag = false;int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]); 
}
void dfs(int u,int x)
{vis[u] = 1;for(auto v : g[u]){if(a[u] >= x && a[v] >= x)flag = true;if(!vis[v])dfs(v,x);}
}void dfs2(int u,int x)
{vis[u] = 1;for(auto v : g[u]){if(!vis[v] && (a[u] >= x) != (a[v] >= x))dfs2(v,x);}
}int check(int x){memset(vis,0,sizeof(vis));flag = false;dfs(s,x);if(flag)return 1;if(a[s] < x && a[t] < x)return false;memset(vis,0,sizeof(vis));dfs2(s,x);if(vis[t] == 1)return 1;elsereturn 0;
}int main()
{cin.tie(0);ios::sync_with_stdio(false);cin>>T;while(T--){cin>>n>>m>>s>>t;for(int i = 1;i <= n;i++){g[i].clear();fa[i] = i;cin>>a[i];}int u,v;for(int i = 1;i <= m;i++){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);fa[find(u)] = find(v);}if(find(s) == find(t)){cout<<"YES"<<endl;int l = 1,r = 1e9;while( l <= r){int m = (l + r) >> 1;if(check(m))l = m + 1;elser = m - 1;}cout<<r<<endl;}elsecout<<"NO"<<endl;}return 0;
}