[POI 20 Stage 3] Tower Defense game

這題蠻有梗的XD 一開始看看起來好難，結果沒想到很簡單XD

作法：

關鍵在於他沒有要求最佳解，而是給一個 k 滿足存在一個 k 個點的點集 P，使得每個點要嘛在點集裡面，要嘛有一個鄰居在點集裡面。有了這個條件，我們只要從 1 開始檢查，如果有一個點還沒被蓋到就直接在他的位置放上強力守衛，這樣就可以在 <= k 次放置內蓋完全部的點了。而證明也不難，因為對於一個還沒被蓋到的點，一定是他落在 P 裡面或是他有一個鄰居落在 P 裡面，所以當在這個點放上強力守衛後，會等價於這個點和所有這個點的鄰居都有了一個一般的守衛，這樣顯然會比只有其中一個點有守衛的情況好，所以當然可以在 k 次以內達到。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=500000+10 ;
 
vector<int> v[maxn] ;
bool vis[maxn] ;
vector<int> ans ;
main()
{
    int n,m,k ; scanf("%d%d%d",&n,&m,&k) ;
    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++) if(!vis[i])
    {
        ans.push_back(i) ; vis[i]=1 ;
        for(int j=0;j<v[i].size();j++)
        {
            int x=v[i][j] ; vis[x]=1 ;
            for(int k=0;k<v[x].size();k++) vis[v[x][k]]=1 ;
        }
    }
    printf("%d\n",ans.size()) ;
    for(int i=0;i<ans.size();i++) printf("%d%c",ans[i],i+1==ans.size()?'\n':' ') ;
}