题解 P6571 【[BOI 2017] Political Development】

· · 题解

翻译者来水个题解。

首先我之前把一句话题意翻错了，翻成了：

给一个图，每个点的度数不超过 k，求最大团。

先考虑这个东西咋做。

不是随便暴力吗。

就很显然地，钦定最大团里的某个点，然后在所有和它相连的点里枚举子集，判断是否可行，复杂度 O(nk^22^k) 过了我请你吃糖。

我们预处理出一个点与哪些点连边，压位处理，这样就 O(nk2^k) 了。

然后考虑原问题，我们想要把它转化成上面这个问题。

可以发现上面这个算法是很浪费的，因为一个子集被算了很多次。我们换个思路，可以枚举最大团里最小的节点，然后在它连向的后面的所有点里枚举子集。

问题是这样还是不能保证边数。可以考虑根据人类智慧构造一个排列，然后按上面的方法搞。

考虑到这个导出子图的度数限制，我们可以想到 dfs 处理，每次 dfs 到一个点就把它所有邻居的 d 值减一，然后如果小于 k 就访问它。

下面证明这个算法一定能得到一个结果：

根据算法可知，如果不能得到一个结果，那么一定是在把所有能访问的点都访问完之后，剩下的点的 d 值全都不小于 k。那么这些点的生成子图不满足题中的性质，矛盾。于是命题得证。

然后有了这个我们就可以像上面一样暴力了，时间复杂度 O(nk2^k)。

#include<algorithm>
#include<vector>
#include<cctype>
#include<cstdio>
using namespace std;
inline int readint(){
    int x=0;
    bool f=0;
    char c=getchar();
    while(!isdigit(c)&&c!='-') c=getchar();
    if(c=='-'){
        f=1;
        c=getchar();
    }
    while(isdigit(c)){
        x=x*10+c-'0';
        c=getchar();
    }
    return f?-x:x;
}
const int maxn=5e4+5;
int n,k,d[maxn];
vector<int> g[maxn],g2[maxn];
int pos[maxn],cnt=0;
bool vis[maxn];
void dfs(int u){
    vis[u]=1;
    pos[u]=cnt++;
    for(int i=0;i<(int)g[u].size();i++){
        int v=g[u][i];
        d[v]--;
        if(d[v]<k&&!vis[v]) dfs(v);
    }
}
bool beside(int u,int v){
    for(int i=0;i<(int)g2[u].size();i++)
        if(g2[u][i]==v) return 1;
    for(int i=0;i<(int)g2[v].size();i++)
        if(g2[v][i]==u) return 1;
    return 0;
}
int g3[maxn];
int calc(int u){
    for(int i=0;i<(int)g2[u].size();i++) g3[g2[u][i]]=0;
    for(int i=0;i<(int)g2[u].size();i++)
        for(int j=0;j<(int)g2[u].size();j++)
            if(i==j) g3[i]|=1<<j;
            else g3[i]|=beside(g2[u][i],g2[u][j])<<j;
    int ans=0;
    for(int i=0;i<(1<<g2[u].size());i++){
        int res=i,cnt=0;
        for(int j=0;j<(int)g2[u].size();j++) if(i>>j&1){
            res&=g3[j];
            cnt++;
        }
        if(res==i) ans=max(ans,cnt);
    }
    return ans+1;
}
int main(){
    #ifdef LOCAL
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    n=readint();
    k=readint();
    for(int i=0;i<n;i++){
        d[i]=readint();
        for(int j=0;j<d[i];j++) g[i].push_back(readint());
    }
    for(int i=0;i<n;i++) if(d[i]<k&&!vis[i]) dfs(i);
    for(int i=0;i<n;i++) for(int j=0;j<(int)g[i].size();j++)
        if(pos[g[i][j]]>pos[i]) g2[i].push_back(g[i][j]);
    int ans=0;
    for(int i=0;i<n;i++) ans=max(ans,calc(i));
    printf("%d\n",ans);
    return 0;
}