题解：P9257 [PA 2022] Mędrcy

· · 题解

缝合题，但是两个 part 都很有意思。

Part 1 题意转化

首先考虑对原题进行转化，对于一个 \set{a,b} 不知道的咒语，我们认为有连边 (a,b)。那么每个人能看到的就是不包含自己的所有连边。而外来者给出的条件就是，图中至少存在一条边。

那你想一个人最开始认为他的度数就是 0，我们希望找到一个时刻 t，使得存在一个人发现他的设想是错的。

如果一个人一条边都看不到，那他肯定 Day 1 就离开了。

如果一个人看到另一个人没有连边，但是他 Day 1 没有离开，那只能是自己有连边了，于是这个人 Day 2 也离开了。

抽象出来就是，假设一个人 x 在第 t 天离开，那么在没有 x 时，应当有人在第 t-1 天离开。

那最小的 t 满足，可以选出一个 t 元点集，使得删掉这么多点后，图中不存在任何边，最小的 t 就是要求出来最小点覆盖。

Part 2 图论处理

一个图的最小点覆盖当然是 NP 问题，但是这里 k\le 30，我们只需要求出 30 的最小点覆盖。

这好像是一个经典问题，但是我确实没做过，非常菜。

每次把度数最大的点拉出来，假设这个点是 u，度数为 d。

我们枚举选择 u 或不选择 u。

选择 u 那么把与 u 相连的边都删掉即可。

不选择 u 那么所有与 u 相连的 d 个点都要选。

记算法的复杂度是 O(nT(k))，那么每次有

T(k)\gets T(k-1)+T(k-d)

发现 d\le 2 的时候，原图是若干条链，容易处理。

于是只需要考虑 d\ge 3，那么 T(k)=T(k-1)+T(k-3)，T(30) 是可以接受的量级。

然后就做完了！时间复杂度 O(T(k)n)。 ::::info[code]

const int N=1e3+5,inf=1e9+7;
int n,m,k,T;
map<pii,int> H;
vector<int> to[N];
int del[N],deg[N];
void add(int a,int b){
    if(H.count(mkp(min(a,b),max(a,b))))return ;
    H[mkp(min(a,b),max(a,b))]=1;
    to[a].pb(b),to[b].pb(a); deg[a]++,deg[b]++;
}
int stk[N],top,cal;
int res[N],tot;
int ans;
void update(int o=1){
    if(o)cal=top;
    if(cal< ans){
        ans=cal,tot=0;
        for(int i=1;i<=n;i++)res[i]=0;
    }
    if(cal==ans){
        for(int i=1;i<=top;i++)if(!res[stk[i]])
            res[stk[i]]=1,tot++;
    }
}
int lid[N];
vector<int> S;
void dfs0(int u){
    S.pb(u);
    for(int v:to[u])if(!del[v])
        if(!lid[v])lid[v]=lid[u]+1,dfs0(v);
}
void calc(){
    cal+=S.size()/2;
    if(S.size()&1){
        for(int v:S)if(lid[v]&1)stk[++top]=v;
    }
    else{
        for(int v:S)stk[++top]=v;
    }
    S.clear();
}
void calc2(){
    cal+=(S.size()+1)/2;
    for(int v:S)stk[++top]=v;
    S.clear();
}
void checkd(){
    int nt=top; cal=top;   
    for(int i=1;i<=n;i++)lid[i]=0;
    for(int i=1;i<=n;i++)if(!del[i] && deg[i]==1)if(!lid[i]){
        lid[i]=2,dfs0(i);
        calc();
    }
    for(int i=1;i<=n;i++)if(!del[i] && deg[i]==2)if(!lid[i]){
        lid[i]=2,dfs0(i);
        calc2();
    }
    update(0);
    top=nt;
}
void erase(int u,int o){
    del[u]=o; if(o)stk[++top]=u; if(!o)top--;
    for(int v:to[u])deg[v]+=o?(-1):1;
}
void dfs(){
    if(top>k)return ;
    int u=0;
    for(int i=1;i<=n;i++)if(!del[i] && deg[i]>deg[u])u=i;
    if(!u)return update();
    if(top==k)return ;
    if(deg[u]<=2)return checkd();
    {
        erase(u,1);
        dfs();
        erase(u,0);
    }
    {
        int _d=deg[u]; vector<int> adj;
        for(int v:to[u])if(!del[v])adj.pb(v);
        for(int v:adj)erase(v,1);
        dfs();
        for(int v:adj)erase(v,0);
    }
}
void solve(){
    n=read(),m=read(),k=read();
    ans=inf,tot=top=0; H.clear();
    for(int i=1;i<=n;i++)to[i].clear(),deg[i]=res[i]=del[i]=0;
    while(m--)add(read(),read());
    dfs();
    if(ans<=k){
        printf("%d %d\n",ans,tot);
        for(int i=1;i<=n;i++)if(res[i])printf("%d ",i);
        printf("\n");
    }
    else printf("-1\n");
}
int main(){
    T=read();
    while(T--)solve();
    return 0;
}
//  Think twice,code once

::::