题目链接 Nudist Beach
来源 Codeforces Round #309 (Div. 1) Problem D
题目大意：
给定一篇森林（共$n$个点），你可以在$n$个点中选择若干个构成一个集合$S$。
输入数据中会给定一些点，你不能选择这些点。
定义$S$中某城市的值：
令$A$= 该城市的在S中的邻居数量 $B$ = 该城市的所有邻居数量
那么$S$中该城市的值为$\frac{A}{B}$
定义$S$的比值为$S$中所有城市的值的最小值
题目的要求是让你确定集合$S$，使得$S$的比值最大
解题思路：
我们可以二分这个比值（在$0$到$1$之间）
然后进行check
check的时候，我们先把所有可以选择的点加入集合。
然后判断这个集合中有没有比值不符合当前check的点
如果有，删除这些不符合的点，并放入队列。
接下来在这些点的邻居中寻找有没有不符合题意的点
如果有，删除这些不符合的点，并放入队列。
就这样一直下去，直到没有点可以删除为止。
最后若集合不为空，则check函数返回true，否则返回false
时间复杂度 $O(Kn)$，$K$为二分次数
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) #define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const double eps = 1e-8; const int N = 100010; int n, m, k; vector <int> v[N]; int deg[N], irr[N], b[N], c[N], g[N], inn[N], ans[N]; int cnt = 0; bool check(double x){ int num = cnt; queue <int> Q; rep(i, 1, cnt) g[c[i]] = 1; rep(i, 1, cnt) inn[c[i]] = deg[c[i]] - irr[c[i]]; rep(i, 1, cnt){ if ((double)(inn[c[i]]) / (double)deg[c[i]] < x){ Q.push(c[i]); g[c[i]] = 0; --num; } } while (!Q.empty()){ int now = Q.front(); Q.pop(); for (auto u : v[now]) if (g[u]){ --inn[u]; if ((double)inn[u] / (double)deg[u] < x){ Q.push(u); g[u] = 0; --num; } } } if (num){ int et = 0; rep(i, 1, cnt) if (g[c[i]]) ans[++et] = c[i]; ans[0] = num; return true; } else return false; } int main(){ scanf("%d%d%d", &n, &m, &k); rep(i, 1, k){ int x; scanf("%d", &x); b[x] = 1; } rep(i, 1, m){ int x, y; scanf("%d%d", &x, &y); v[x].push_back(y); v[y].push_back(x); ++deg[x], ++deg[y]; if (b[x]) ++irr[y]; if (b[y]) ++irr[x]; } double l = 0.00, r = 1.00; cnt = 0; rep(i, 1, n) if (!b[i]) c[++cnt] = i; rep(i, 1, 100){ double mid = (l + r) / 2; if (check(mid)) l = mid; else r = mid - eps; } printf("%d\n", ans[0]); rep(i, 1, ans[0]) printf("%d ", ans[i]); putchar(10); return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/7194079.html
