记$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 }
View Code
原文地址：http://www.cnblogs.com/PYWBKTDA/p/16814566.html
