[luogu6575]Friends

记$s=p+q$，当存在一个点度数$\ge s$时，显然无解

记$d_{S,T}=\sum_{x\in S,y\in T}[(x,y)\in E]$，称$S\subseteq V$合法当且仅当$|S|\le p$且$d(S,V\backslash S)\le q$

结论：若$S$和$T$合法，则$S\backslash T$和$T\backslash S$中存在一个合法

设$\begin{cases}A=S\backslash T,B=T\backslash S\\C=S\cap T,D=V\backslash (S\cup T)\end{cases}$，则$\begin{cases}d(A\cup C,B\cup D)\le q\\d(B\cup C,A\cup D)\le q\end{cases}$

反证法，假设两者均不合法，显然大小均$\le p$，即$\begin{cases}d(A,B\cup C\cup D)>q\\d(B,A\cup C\cup D)>q\end{cases}$

将上项两对式子者分别相加，即
$$
d(A\cup C,B\cup D)+d(B\cup C,A\cup D)\le 2q<d(A,B\cup C\cup D)+d(B,A\cup C\cup D)
$$
将其按"分配律"展开后，可得$d(C,D)<0$，矛盾

换言之，仅需对每个点找出一个包含其的合法集合，并通过上述方式消除重复元素即可

关于找合法集合，以该点为作为$S$，并不断决策某个与$S$相邻的点是否加入$S$

注意到每次决策后，至少使$|S|$或$d(S,V\backslash S)$增加$1$，因此至多决策$s$次

用set维护这些待决策点（超过$s$个即退出），每次决策后需要$O(s\log s)$处理影响

关于消除重复元素，至多$O(ns)$次，每次可以$O(n)$找出一对并$O(s^{2})$消除

综上，时间复杂度为$O(ns2^{s}\log s+n^{2}s+ns^{3})$，且跑不满，可以通过

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=2505;
  4 int n,m,p,q,x,y,bl[N],d[N],vis[N][N];
  5 vector<int>v0,e[N],v[N];set<int>S;
  6 bool dfs(int s1,int s2){
  7     if ((s1>p)||(s2>q))return 0;
  8     if (S.empty())return 1;
  9     int x=(*S.begin()),s=d[x];
 10     d[x]=-2,S.erase(x);
 11     if (dfs(s1,s2+s))return 1;
 12     d[x]=-1;
 13     for(int j:e[x]){
 14         if (d[j]==-2)s2++;
 15         if ((d[j]>=0)&&(++d[j]==1))S.insert(j);
 16     }
 17     if (dfs(s1+1,s2))return 1;
 18     d[x]=s,S.insert(x);
 19     for(int j:e[x])
 20         if ((d[j]>0)&&(--d[j]==0))S.erase(j);
 21     return 0;
 22 }
 23 int main(){
 24     scanf("%d%d%d",&n,&p,&q);
 25     for(int i=1;i<=n;i++){
 26         scanf("%d",&x);
 27         for(int j=1;j<=x;j++){
 28             scanf("%d",&y);
 29             vis[i][y+1]=1,e[i].push_back(y+1);
 30         }
 31     }
 32     for(int i=1;i<=n;i++){
 33         if (e[i].size()>=p+q){
 34             puts("detention");
 35             return 0;
 36         }
 37         for(int j=i+1;j<=n;j++)
 38             if (vis[i][j]^vis[j][i]){
 39                 puts("detention");
 40                 return 0;
 41             }
 42     }
 43     for(int i=1;i<=n;i++)
 44         if (!bl[i]){
 45             memset(d,0,sizeof(d));
 46             d[i]=-1,S.clear();
 47             for(int j:e[i])d[j]=1,S.insert(j);
 48             if (!dfs(1,0)){
 49                 puts("detention");
 50                 return 0;
 51             }
 52             m++;
 53             for(int j=1;j<=n;j++)
 54                 if (d[j]==-1){
 55                     bl[j]=1;
 56                     v[m].push_back(j);
 57                 }
 58         }
 59     while (1){
 60         x=y=0;
 61         memset(bl,0,sizeof(bl));
 62         for(int i=1;i<=m;i++){
 63             for(int j:v[i]){
 64                 if (!bl[j])bl[j]=i;
 65                 else{
 66                     x=i,y=bl[j];
 67                     break;
 68                 }
 69             }
 70             if ((x)&&(y))break;
 71         }
 72         if ((!x)&&(!y))break;
 73         int cnt=0;
 74         memset(bl,0,sizeof(bl));
 75         for(int i:v[x])bl[i]|=1;
 76         for(int i:v[y])bl[i]|=2;
 77         for(int i=1;i<=n;i++)
 78             if (bl[i]==1){
 79                 for(int j:e[i])
 80                     if ((bl[j]!=1)&&(++cnt>q))break;
 81                 if (cnt>q)break;
 82             }
 83         if (cnt<=q){
 84             v[x].clear();
 85             for(int i=1;i<=n;i++)
 86                 if (bl[i]==1)v[x].push_back(i);
 87         }
 88         else{
 89             v[y].clear();
 90             for(int i=1;i<=n;i++)
 91                 if (bl[i]==2)v[y].push_back(i);
 92         }
 93     }
 94     puts("home");
 95     int cnt=0;
 96     for(int i=1;i<=m;i++)
 97         if (!v[i].empty())cnt++;
 98     printf("%d\n",cnt);
 99     for(int i=1;i<=m;i++)
100         if (!v[i].empty()){
101             printf("%d ",v[i].size());
102             for(int j:v[i])printf("%d ",j-1);
103             printf("\n");
104         }
105     return 0;
106 }