2015年6月26日 星期五

[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') ;
}
 

沒有留言:

張貼留言