原題鏈接：https://ac.nowcoder.com/acm/contest/9985/A
目錄
- 題意
- 分析
- Code
題意
有n個點，m條邊，每個點有一個全值，起點是s，終點是t，設美麗路徑為s到t路程中第k/2+1小的數，求最大的美麗值是多少，
分析
剛開始的想法是找到最大的相鄰兩點中的較小值，最后被證明錯了，賽中也有很多人這樣過了，后來資料加強了，
既然不能貪心，只能用二分去取答案，我們把大于等于mid的權值設為1，小于等于mid為0，因為我們要求k/2+1小的數，即路徑中第k/2+1小的數是1，
- 用并查集維護起點和終點，直接判-1的情況
- 如果有連著的兩個1，那么最后結果一定是大于mid，因為可以來回一直走這兩個1
- 去掉上述情況之后要使1的個數大于等于0，起點和終點不能都是0，所以我們第二遍從起點出發沿著101010…這樣找下去，如果可以到終點，那么就是可以的
Code
#include <bits/stdc++.h>
using namespace std;
//#define ACM_LOCAL
#define fi first
#define se second
#define il inline
#define re register
typedef long long ll;
typedef pair<int, int> PII;
typedef unsigned long long ull;
const int N = 2e5 + 10;
const int M = 1e6 + 10;
const ll INF = 1e18 + 5;
const double eps = 1e-5;
const int MOD = 998244353;
int fa[N], val[N], vis[N], n, m, s, t, flag;
vector<int> g[N];
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
void dfs(int x, int mid) {
vis[x] = 1;
for (auto v : g[x]) {
if (val[x] >= mid && val[v] >= mid) flag = 1;
if (!vis[v]) dfs(v, mid);
}
}
void dfs2(int x, int mid) {
vis[x] = 1;
for (auto v : g[x]) {
if (!vis[v] && (val[x] >= mid) != (val[v] >= mid)) dfs2(v, mid);
}
}
bool check(int x) {
flag = 0;
memset(vis, 0, sizeof vis);
dfs(s, x);
if (flag) return true;
if (val[s] < x && val[t] < x) return false;
memset(vis, 0, sizeof vis);
dfs2(s, x);
if (vis[t]) return true;
else return false;
}
void solve() {
int T; cin >> T; while (T--) {
cin >> n >> m >> s >> t;
for (int i = 1; i <= n; i++) cin >> val[i], fa[i] = i, g[i].clear();
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
fa[find(u)] = find(v);
}
if (find(s) != find(t)) {
printf("NO\n");
continue;
}
printf("YES\n");
int l = 1, r = 1e9;
while (l <= r) {
int mid = (l + r) >> 1;
if (check(mid)) l = mid + 1;
else r = mid - 1;
}
printf("%d\n", r);
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#ifdef ACM_LOCAL
freopen("input", "r", stdin);
freopen("output", "w", stdout);
#endif
solve();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/262951.html
標籤：其他
下一篇：Android學習--布局