【二分】2021牛客寒假算法基础集训营5 A美丽的路径
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【二分】2021牛客寒假算法基础集训营5 A美丽的路径,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含3141字,纯文字阅读大概需要5分钟。
内容图文
![【二分】2021牛客寒假算法基础集训营5 A美丽的路径](/upload/InfoBanner/zyjiaocheng/603/b547ee3777cb4bfd9fc454cbe46b792c.jpg)
题目大意
有n个点,m条边,每个点有一个权值。起点是s,终点是t,设美丽路径为s到t路程中第k/2+1小的数,求最大的美丽值是多少。
解题思路
二分去取答案。我们把大于等于mid的权值设为1,小于mid为0。因为我们要求k/2+1小的数,即路径中第k/2+1小的数是1,1的个数要大于等于0的个数。
-
用并查集维护起点和终点,直接判-1的情况
-
如果有连着的两个1,那么最后结果一定是大于mid,因为可以来回一直走这两个1
-
去掉上述情况之后要使1的个数大于等于0,有两种情况:
- 点数为奇数,则要满足类似
10101...1
的结构。 - 点数为偶数,满足
1010..10
或0101..01
即可,即 0 0 0 和 1 1 1 交替出现。
实际实现的时候,只需要满足以下条件:
- 不论是奇数还是偶数,都满足路径上相邻的两点标记不同。
- 若为奇数,最后的标记是 1 1 1。
- 点数为奇数,则要满足类似
注意事项
1.二分的左端点为读入的最小值,右端点为最大值,可以使程序跑的快一点。
参考代码
#include<stdio.h>
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
#include<climits>
#include<cmath>
#include<algorithm>
#include<queue>
#include<deque>
#include<map>
#include<unordered_map>
#include<set>
#include<stack>
//#define LOCAL //提交时一定注释
#include<bits/stdc++.h>
#define VI vector<int>
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long LL;
typedef double db;
const int inf = 0x3f3f3f3f;
const LL INF = 1e18;
const int N = 2e5 + 10;
const LL mod = 998244353;
const int p = 26;
inline int readint() {int x; scanf("%d", &x); return x;}
int w[N], fa[N];
int head[N], Next[N << 1], edge[N << 1];
int tot;
int n, m, s, e;
bool vis[N];
bool flag;
void init() {
for(int i = 1; i <= n; ++i) {
fa[i] = i;
head[i] = 0;
}
tot = 0;
}
void add(int u, int v) {
edge[++tot] = v;
Next[tot] = head[u];
head[u] = tot;
}
int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
bool dfs(int x, int mid) {
vis[x] = true;
for(int i = head[x]; i; i = Next[i]) {
int k = edge[i];
if (w[x] >= mid && w[k] >= mid) {
return true;
}
if (!vis[k] && dfs(k, mid)) return true;
}
return false;
}
bool dfs2(int x, int mid, int dep) {
if (x == e) {
if (((dep & 1) && w[x] >= mid) || !(dep & 1)) //只需要判断终点的情况
return true;
}
vis[x] = true;
for(int i = head[x]; i; i = Next[i]) {
int k = edge[i];
if (vis[k]) continue;
if (w[x] < mid && w[k] < mid) return false; //因为第一个dfs已经判过两个都大于等于mid的情况,这里只要判断都小于mid的情况。即不满足相邻的两个不同
if (dfs2(k, mid, dep + 1)) return true;
}
return false;
}
bool check(int mid) {
memset(vis, 0, sizeof(vis));
if (dfs(s, mid)) return true;
memset(vis, 0, sizeof(vis));
return dfs2(s, mid, 1);
}
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t; t = readint();
while (t--) {
init();
scanf("%d%d%d%d", &n, &m, &s, &e);
VI g[n + 1];
int minn = inf, maxx = -1;
for(int i = 1; i <= n; i++) {
w[i] = readint();
maxx = max(maxx, w[i]);
minn = min(minn, w[i]);
}
for(int i = 1; i <= m; i++) {
int x = readint(), y = readint();
add(x, y); add(y, x);
fa[find(x)] = find(y);
}
if (find(s) != find(e)) {
printf("NO\n");
continue;
}
int l = minn, r = maxx;
int ans = 0;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) {
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
if (ans == 0) printf("NO\n"); //答案没有更新
else {
printf("YES\n%d\n", ans);
}
}
return 0;
}
内容总结
以上是互联网集市为您收集整理的【二分】2021牛客寒假算法基础集训营5 A美丽的路径全部内容,希望文章能够帮你解决【二分】2021牛客寒假算法基础集训营5 A美丽的路径所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。