[CF 553D] Nudist Beach

作法：

考慮二分搜答案，那麼可以先對每個點算出「如果取他的話至少要取幾個他的鄰居」，以下稱其為$num$值，再來要判斷是否有可能。最好的情況是取下了所有非堡壘的點，因為這時每個點可以獲得最多的被取到的鄰居數，但有些點儘管如此還是不能被取的，他們就是「$num$值大於鄰居中非堡壘點」的點，所以必須先把他們去除掉。把他們去除後又可能多了一些新的不能取的點，因此就可以得到這會是某種BFS的過程：先把一開始的$k$個點標成不可取他的，並推入 queue 中，每次從 queue 取出一個點時，更新他所有鄰居的「當前還有幾個鄰居是可以被取的」的值，如果發現有一個鄰居的值已經$<$他的$num$值時就也把他推入 queue 裡面。過程結束後如果還有沒被BFS到的點那麼就是可行的，否則不行，這個算法的充要條件證明則算是顯然的。

code :

#include<bits/stdc++.h>
#define DB double
using namespace std;
const int maxn=100000+10 ;
 
vector<int> v[maxn] ;
int deg[maxn],fort[maxn],n,k ;
int num[maxn],d[maxn] ;
 
queue<int> q ;
bool vis[maxn] ;
int BFS(DB rat)
{
    for(int i=1;i<=n;i++)
        num[i]=ceil(deg[i]*rat) ,
        d[i]=deg[i] ;
    memset(vis,0,sizeof(vis)) ;
    for(int i=1;i<=k;i++) vis[fort[i]]=1 , q.push(fort[i]) ;
 
    int ret=0 ;
    while(!q.empty())
    {
        ret++ ;
        int u=q.front() ; q.pop() ;
        for(auto i : v[u]) if(!vis[i])
        {
            d[i]-- ;
            if(d[i]<num[i]) vis[i]=1 , q.push(i) ;
        }
    }
    return ret ;
}
 
main()
{
    int m ; scanf("%d%d%d",&n,&m,&k) ;
    for(int i=1;i<=k;i++) scanf("%d",&fort[i]) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    for(int i=1;i<=n;i++) deg[i]=v[i].size() ;
    DB l=0 , r=1 ;
    while(r-l>1e-8)
    {
        DB mid=(r+l)/2 ;
        if(BFS(mid)==n) r=mid ;
        else l=mid ;
    }
    BFS(l) ;
    int ans=0 ;
    for(int i=1;i<=n;i++) if(!vis[i]) ans++ ;
    printf("%d\n",ans) ;
    for(int i=1;i<=n;i++) if(!vis[i]) printf("%d%c",i,--ans?' ':'\n') ;
}