本文主要是介绍codeforces 553D Nudist Beach 二分+bfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
題意：
給你n个点，然后让你选出一些点，使得每个点的比率最小值尽量大，让你输出你所选的点。
其中有m个点是不能选的。k条无向边，连接着点与点，保证只有一个连通块）。
点x的比率= （点x的邻居，且在你所选的点集内）/（点x的所有邻居）。
思路：
二分、bfs
二分比率(0～1).
首先，我们假设所有可以选入的点都已经选进来，计算每个点的ratio，对于ratio < mid的点，扔到队列中，相当于排除掉这个点。
然后bfs，将排除某些点后的其他点ratio值更新，如果更新后该点的ratio值 < mid，同样扔到队列中。
最后查看所选入的点集是否还有没有被排除的，有则说明存在方案。
code：
#include <bits/stdc++.h>
using namespace std;const int N = 1e5+5;
const double eps = 1e-9;
typedef long long LL;int n, m, k;
int a[N];
vector <int> vec[N];
bool ban[N], res[N];
int deg[N], bad[N];
//double rat[N];
bool vis[N];
int cot[N];inline int dcmp(double t) {if(fabs(t) <= eps) return 0;return t < 0?-1:1;
}
bool check(double mid) {queue <int> q;memset(vis, false, sizeof(vis));memset(cot, 0, sizeof(cot));for(int i = 1;i <= n; i++) {double rat = 1.0-(double)bad[i]/deg[i];if(!ban[i]&&dcmp(rat-mid) < 0) {q.push(i);vis[i] = true;}if(ban[i]) vis[i] = true;}while(!q.empty()) {int u = q.front(); q.pop();for(auto &i:vec[u]) {if(vis[i]) continue;cot[i]++;double rat = 1.0-(double)(bad[i]+cot[i])/deg[i];if(dcmp(rat-mid) < 0) {q.push(i);vis[i] = true;}}}for(int i = 1;i <= n; i++) if(!vis[i]) return true;return false;
}void solve() {double l = 0, r = 1;int ti = 100;while(ti--) {double mid = (l+r)/2;if(check(mid)) {for(int i = 1;i <= n; i++)res[i] = vis[i];l = mid;}else r = mid;}int cnt = 0;for(int i = 1;i <= n; i++)if(!res[i]) cnt++;printf("%d\n", cnt);for(int i = 1;i <= n; i++)if(!res[i]) printf("%d ", i);puts("");
}int main() {scanf("%d%d%d", &n, &m, &k);int t;for(int i = 0;i < k; i++) {scanf("%d", &t);ban[t] = true;}int u, v;for(int i = 0;i < m; i++) {scanf("%d%d", &u, &v);vec[u].push_back(v);vec[v].push_back(u);deg[u]++, deg[v]++;if(ban[u]) bad[v]++;if(ban[v]) bad[u]++;}solve();return 0;
}这篇关于codeforces 553D Nudist Beach 二分+bfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
