叶妺妺非常喜欢图论题,这天她出了一个图论题,有一个 \(n\) 个点 \(m\) 条边的无向图,其中第 \(i\) 个点的点权为 \(a_{i}\) ,她定义一 条点数为 \(k\) 路径: \(b_{1}, b_{2} , \ldots, b_{k}\) ;其中点 \(b_{i-1}\) 与点 \(b_{i}\) 通过一条边直接相连 \((2 \leq i \leq k)\) ,所以路径中可以出现重复 的点。她将一条路径的美丽值定义为:假设这条路径的点数为 \(k\) ,那么这条路径的美丽值就是此路径上的所有点的点 权中第 \([k / 2+1\rfloor\) 小的点权。现在她会询问你是否存在起点为 \(s\) 号点并且终点为 \(t\) 号点的路径,如果存在则先输出 \(Y E S\) ,再输出存在的所有路径中的最大的美丽值;否则直接输出 \(N O\) 。
有多组样例, 第一行输入一个数 \(T\), 表述样例组数
对于每组样例, 第一行先输入四个数 \(n, m, s, t\), 保证 \(1 \leq s \leq n, 1 \leq t \leq n\)
第二行输入 \(n\) 个数, 其中第 \(i\) 个数为 \(a_{i}\), 表示第 \(i\) 个点的点权
接下来输入 \(m\) 行, 第 \(i\) 行输入两个数 \(x_{i}\) 和 \(y_{i}\), 表示点 \(x_{i}\) 与点 \(y_{i}\) 之间有一条无向边, 保证 \(1 \leq x_{i} \leq n, 1 \leq y_{i} \leq\) \(n\)
【数据规模与约定】
如果存在起点为 \(s\) 号点并且终点为 \(t\) 号点的路径, 则第一行输出 \(Y E S\), 第二行输出存在的所有的路径中的最大的 美丽值; 否则直接输出 \(N O\)
1 5 4 2 4 1 2 3 4 5 1 2 2 3 3 4 4 5
YES 4
二分,dfs
二分答案 \(w\),如果 \(s\) 到 \(t\) 的路径上存在相邻的节点点权都大于或等于 \(w\),则由于可以在两点之间无限徘徊使得中位数大于等于当前答案,说明答案可能会更大,另外如果存在一条 \(s\) 到 \(t\) 的路径中大于等于 \(w\) 的点的个数不少于少于 \(w\) 的点的个数,也说明答案可能会更大,其他情况说明答案大了
// Problem: 美丽的路径 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/30977/A // Memory Limit: 524288 MB // Time Limit: 6000 ms // // Powered by CP Editor (https://cpeditor.org) // %%%Skyqwq #include <bits/stdc++.h> //#define int long long #define help {cin.tie(NULL); cout.tie(NULL);} #define pb push_back #define fi first #define se second #define mkp make_pair using namespace std; typedef long long LL; typedef pair<int, int> PII; typedef pair<LL, LL> PLL; template <typename T> bool chkMax(T &x, T y) { return (y > x) ? x = y, 1 : 0; } template <typename T> bool chkMin(T &x, T y) { return (y < x) ? x = y, 1 : 0; } template <typename T> void inline read(T &x) { int f = 1; x = 0; char s = getchar(); while (s < '0' || s > '9') { if (s == '-') f = -1; s = getchar(); } while (s <= '9' && s >= '0') x = x * 10 + (s ^ 48), s = getchar(); x *= f; } const int N=2e5+5; int n,m,s,t,a[N]; bool v[N],vis[N]; vector<int> adj[N]; bool f; bool ck(int x) { for(int i=1;i<=n;i++) if(v[i]&&a[i]>=x) for(int j:adj[i]) if(v[j]&&a[j]>=x)return true; return false; } void ck1(int x,int s1,int s2,int w) { vis[x]=true; if(x==t) { if(s1>=s2)f=true; return ; } for(int y:adj[x]) { if(vis[y])continue; ck1(y,s1+(a[y]>=w),s2+(a[y]<w),w); } } void dfs(int x) { v[x]=true; for(int y:adj[x]) if(!v[y])dfs(y); } int main() { int T; for(cin>>T;T;T--) { cin>>n>>m>>s>>t; int r=0; for(int i=1;i<=n;i++)cin>>a[i],r=max(r,a[i]),adj[i].clear(); while(m--) { int x,y; cin>>x>>y; adj[x].pb(y),adj[y].pb(x); } memset(v,0,sizeof v); dfs(s); if(!v[t]) { puts("NO"); continue; } int l=0; while(l<r) { int mid=l+r+1>>1; f=false; for(int i=1;i<=n;i++)vis[i]=0; ck1(s,a[s]>=mid,a[s]<mid,mid); if(f||ck(mid))l=mid; else r=mid-1; } puts("YES"),cout<<l<<'\n'; } return 0; }