codeforces 553D . Nudist Beach 二分

题目链接

有趣的题。

给一个图， n个点m条边。 有k个点不可选择。

现在让你选出一个非空的点集， 使得点集中strength最小的点的strength最大。

strength的定义：一个点周围的点中在集合里的点/一个点周围的点。

我们二分这个strength值。

每次二分， 我们遍历每个点， 然后将strength值小于mid的点加到队列里面，然后标记一下， 相当于将这个点去除掉。

然后遍历队列， 将队列里的点周围的点strength值小于mid的加进队列，标记， 不断重复。

最后看有没有点没有被标记就好。

具体看代码。

#include <iostream>

#include <vector>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <complex>

#include <cmath>

#include <map>

#include <set>

#include <string>

#include <queue>

#include <stack>

#include <bitset>

using namespace std;

#define pb(x) push_back(x)

#define ll long long

#define mk(x, y) make_pair(x, y)

#define lson l, m, rt<<1

#define mem(a) memset(a, 0, sizeof(a))

#define rson m+1, r, rt<<1|1

#define mem1(a) memset(a, -1, sizeof(a))

#define mem2(a) memset(a, 0x3f, sizeof(a))

#define rep(i, n, a) for(int i = a; i<n; i++)

#define fi first

#define se second

typedef complex <double> cmx;

typedef pair<int, int> pll;

const double PI = acos(-1.0);

const double eps = 1e-8;

const int mod = 1e9+7;

const int inf = 1061109567;

const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

const int maxn = 1e5+5;

int n, m, k;

int a[maxn], vis[maxn], ans[maxn], ban[maxn], de[maxn], num[maxn];

vector <int> g[maxn];

int dblcmp(double x) {

    if(fabs(x)<eps)

        return 0;

    return x<0?-1:1;

}

int check(double ratio) {

    queue <int> q;

    mem(vis);

    mem(num);

    for(int i = 1; i <= n; i++) {

        if(ban[i]) {

            vis[i] = 1;

            continue;

        }

        double tmp = 1-1.0*a[i]/de[i];

        if(dblcmp(tmp-ratio)<0) {

            q.push(i);

            vis[i] = 1;

        }

    }

    while(!q.empty()) {

        int u = q.front(); q.pop();

        for(auto &i : g[u]) {

            if(ban[i] || vis[i])

                continue;

            num[i]++;

            double tmp = 1-1.0*(a[i]+num[i])/de[i];

            if(dblcmp(tmp-ratio)<0) {

                q.push(i);

                vis[i] = 1;

            }

        }

    }

    for(int i = 1; i <= n; i++) {

        if(!vis[i])

            return 1;

    }

    return 0;

}

void solve() {

    double l = 0, r = 1;

    for(int i = 0; i < 100; i++) {

        double mid = (l+r)/2;

        if(check(mid)) {

            for(int j = 1; j <= n; j++) {

                ans[j] = vis[j];

            }

            l = mid;

        } else {

            r = mid;

        }

    }

    int cnt = 0;

    for(int i = 1; i <= n; i++)

        if(!ans[i])

            cnt++;

    cout<<cnt<<endl;

    for(int i = 1; i <= n; i++)

        if(!ans[i])

            cout<<i<<" ";

}

int main()

{

    int x, u, v;

    cin>>n>>m>>k;

    for(int i = 0; i < k; i++) {

        scanf("%d", &x);

        ban[x] = 1;

    }

    for(int i = 0; i < m; i++) {

        scanf("%d%d", &u, &v);

        g[u].pb(v);

        g[v].pb(u);

        de[u]++, de[v]++;

        if(ban[u])

            a[v]++;

        if(ban[v])

            a[u]++;

    }

    solve();

    return 0;

}