codeforces #309 D D. Nudist Beach(浮點數二分+bfs)

題目連結：

點選打開連結

題目大意：

給出一個連通圖選取一個子圖，給出不能被選中點，每個點的值為（子圖的度數/總度數），求一個最小值最大的子圖

題目分析：

很顯然這是一個二分圖，因為如果存在x能選出子圖，那麼一定存在x2<x也能成立

那麼現在如何判斷二分的函數才是關鍵

構造的方法常見的就兩種，一種是取空集，然後看見符合條件加到集合中，一種就是取全集，看見不合适的踢出去，這道題适合第二種，找出集合中不符合條件的點剔除去，因為隻有剔除取的點相連的點才可能成為新的不符合條件的點，那麼如此看來這符合寬搜的羅輯，那麼我們就可以通過寬搜解決這一問題

對于浮點數，我總是有一種莫名的恐懼，果然wa了無數次。。。。。還是弱啊，對浮點數缺乏控制力，但還是守住了底線，一定要自己實作的代碼ac，雖然耗費了大半天....

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#define MAX 100007
#define eps 1e-9

using namespace std;

int n,m,k,u,v,cnt;
bool used[MAX];
int num[MAX],total[MAX];
double r[MAX];
bool ban[MAX];
bool res[MAX];
vector<int> e[MAX];

int cmp ( double t )
{
    if ( fabs(t) <= eps ) return 0;
    return t < 0 ? -1:1;
}

void clear ( )
{
    memset ( ban , 0 , sizeof ( ban ) );
    memset ( num , 0 , sizeof ( num ) );
    memset ( total , 0 , sizeof ( total ) );
    memset ( used , 0 , sizeof ( used ) );
    for ( int i = 0 ; i < MAX ; i++ )
       e[i].clear();
}

bool check ( double x )
{
    queue<int> q;
    memset ( used , 0 , sizeof ( used ) );
    for ( int i = 1 ; i <= n ; i++ )
    {
        r[i] = num[i]*1.0/total[i];
        if ( ban[i] ) r[i] = -1;
        if ( cmp(r[i]-x) < 0 )
        {
            q.push ( i );
            used[i] = true;
        }
    }
    //cout << "YES : " <<r[2]-x <<" " << used[2] << endl;
    cnt = n;
    while ( !q.empty() )
    {
        int u = q.front();
        q.pop();
        cnt--;
        int len = e[u].size();
        for ( int i = 0 ; i < len ; i++ )
        {
            int v = e[u][i];
            if ( used[v] ) continue;
            r[v] -= 1.0/total[v];
            //if ( r[v] < x )
            if ( cmp ( r[v] - x ) < 0 )
            {
                q.push ( v );
                used[v] = true;
            }
        }
    }
    return cnt;
}

int main ( )
{
    while ( ~scanf ( "%d%d%d" , &n , &m , &k ) )
    {
        clear();
        for ( int i = 0 ; i < k ; i++ )
        {
            scanf ( "%d" , &u );
            used[u] = true;
            ban[u] = true;
        }
        for ( int i = 0 ; i < m ; i++ )
        {
            scanf ( "%d%d" , &u , &v );
            total[u]++;
            total[v]++;
            if ( used[u] || used[v] ) continue;
            num[u]++;
            num[v]++;
            e[u].push_back ( v );
            e[v].push_back ( u ); 
        }
        double l = 0 , r = 1 , mid;
        int times = 100;
        int ans_cnt;
        while ( times-- )
        {
            mid = (l+r)/2.0;
            //cout << l << " " << r << endl;
            if ( check ( mid ) ) 
            {
                ans_cnt = cnt;
                for ( int i = 1 ; i <= n ; i++ )
                    res[i] = used[i];
                l = mid;
            }
            else r = mid;
        }
        printf ( "%d\n" , ans_cnt );
        for ( int i = 1 ; i <= n ; i++ )
            if ( !res[i] ) 
                printf ( "%d " , i );
        puts("");
    }
}