「PA2022」Medrcy

设 \(f_i\) 表示第 \(i\) 个人知道的咒语集合，\(c_i\) 为其补集，那么第 \(i\) 个人第 \(k\) 天会离开当且仅当存在一个序列 \(a_{1\sim k-1}\)，使得 \(\bigcup\limits_{j=1}^{k-1}(f_i \cup f_{a_j})=\varnothing\)，即 \(\bigcap_{j=1}^{k-1}(c_i \cap c_{a_j})=\text{U}\)。

考虑连接 \((a_i,b_i)\)，那么第一次有人没来聚会的天数为最小点覆盖数 \(k\)（选取最少的点使得它们能覆盖图中所有的边），第 \(i\) 个人第 \(k\) 天会离开当且仅当存在一种最小点覆盖方案使得选择了节点 \(i\)，注意到如果不选一个点就一定会选择它的所有邻居，搜索时可以优先选择度数最大的点进行操作，若此点度数不大于 \(2\) 而会使时间复杂度错误，但此时原图一定由若干环或链组成，根据奇偶性直接判断即可，复杂度为 \(T(k)=T(k-1)+T(k-3) \approx 10^5\)。

#include<bits/stdc++.h>
using namespace std;
int t,n,m,k,a,b,sum,cnt,ans[1001],vis[1001],use[1001],aus[1001];
set <int> G[1001];
basic_string <int> S;
void loop(int x){
    use[x]=1,S+=x;
    for(int y:G[x]) if(!use[y]) loop(y);
}
void dfs(int v){
    if(v>k) return;
    int d=1,w=0;
    for(int i=1;i<=n;i++) if(G[i].size()>G[d].size()) d=i;
    if(G[d].size()<=2){
        int now=v;
        for(int i=1;i<=n;i++) use[i]=0,aus[i]=vis[i];
        for(int i=1;i<=n;i++){
            if(!use[i]&&G[i].size()==1){
                S.clear(),loop(i),now+=S.size()/2;
                if(S.size()&1) for(int j=1;j<S.size()-1;j+=2) aus[S[j]]=1;
                else for(int j:S) aus[j]=1;
            }
        }
        for(int i=1;i<=n;i++){
            if(!use[i]&&G[i].size()>1){
                S.clear(),loop(i),now+=(S.size()+1)/2;
                for(int j:S) aus[j]=1;
            }
        }
        if(now<=k){
            if(now<sum) sum=now,memset(ans,0,sizeof(ans));
            if(now==sum) for(int i=1;i<=n;i++) ans[i]|=aus[i];
        }
        return;
    }
    vector <pair<int,int>> now;
    for(int i:G[d]) now.push_back({i,d}),G[i].erase(d);
    G[d].clear(),vis[d]=1,dfs(v+1),vis[d]=0;
    for(auto [u,v]:now) G[u].insert(v),G[v].insert(u);
    now.clear(),w=G[d].size(),S.clear();
    for(int i:G[d]) S+=i;
    for(int i:S) for(int j:G[i]) now.push_back({i,j}),G[j].erase(i);
    for(int i:S) vis[i]=1,G[i].clear();
    dfs(v+w);
    for(auto [u,v]:now) G[u].insert(v),G[v].insert(u);
    for(int i:G[d]) vis[i]=0;
}
int main(){
	scanf("%d",&t);
    while(t--){
        scanf("%d%d%d",&n,&m,&k),cnt=0,sum=1e9;
        for(int i=1;i<=n;i++) G[i].clear(),ans[i]=0;
        for(int i=1;i<=m;i++) scanf("%d%d",&a,&b),G[a].insert(b),G[b].insert(a);
        dfs(0);
        if(sum==1e9) printf("-1\n");
        else{
            for(int i=1;i<=n;i++) cnt+=ans[i];
            printf("%d %d\n",sum,cnt);
            for(int i=1;i<=n;i++) if(ans[i]) printf("%d ",i);
            printf("\n");
        }
    }
    return 0;
}