bzoj2215: [Poi2011]Conspiracy

Description

Byteotia的领土被占领了，国王Byteasar正在打算组织秘密抵抗运动。国王需要选一些人来进行这场运动，而这些人被分为两部分：一部分成为同谋者活动在被占领区域，另一部分是后勤组织在未被占领的领土上运转。但是这里出现了一个问题： 1. 后勤组织里的任意两人都必须是熟人，以促进合作和提高工作效率。 2. 同谋者的团体中任意两人都不能是熟人。 3. 每一部分都至少要有一个人。国王想知道有多少种分配方案满足以上条件，当然也有可能不存在合理方案。现在国王将这个问题交由你来解决！

Input

第一行一个整数n（2<=n<=5000）表示有n个人参与该抵抗运动，标号为1..n。之后有n行，第i行的第一个数ki（0<=ki<=n-1）表示i认识ki个人,随后的ki个数表示i的熟人。 p.s.输入满足：如果i是x的熟人，x会在i的序列中出现同时i也会出现在x的熟人序列中。

Output

符合条件的方案总数。

Sample Input

4
2 2 3
2 1 3
3 1 2 4
1 3

Sample Output

HINT

Hint 1和4分到同谋者组织，2和3为后勤组织。 2和4分到同谋者组织，1和3为后勤组织。 4单独分到同谋者组织，1和2、3为后勤组织。

题解：

考虑构造一组可行解，把每个点拆成两个点x0，x1，x0表示后勤组织，x1表示同谋者。

若x与y认识，则x1向y0连边。

若x与y不认识，则x0向y1连边。

如此求出一组2-SAT的可行解，如果无解则答案为0。

若有解，那么最多只能把一个人从后勤组织改为同谋者，也最多只能把一个人从同谋者改为后勤组织，也可以将一个在同谋者另一个在后勤组织的两个人交换。

显然不能直接暴力搞

先预处理出每个点和它相冲突的点的个数和其中任意一个冲突点的编号

冲突点定义为假如把这个点放到对面去，对面的点中会和这个点发生冲突的点

举个例子，假如两个人u和v，u在后勤，v在同谋者，而u，v互相认识，则v是u的矛盾点

或者是两个人a和b，a在同谋者，b在后勤，而a，b不认识，这b是a的矛盾点

先讨论要交换的情况

显然，当一个点的矛盾点数量超过2，他既不能直接去对面，也不能和对面的某个人直接交换

当一个点u的矛盾点为1时，设它的矛盾点为v

　　假如v也只有一个矛盾点，且v的矛盾点是u，显然这两人可以交换（注意不要重复计算）

　　假如v没有矛盾点，显然可以直接交换

设在后勤组织中没有矛盾点的个数为t0，同谋者中没有矛盾点的个数为t1，显然这两类点可以任取一对来交换，方案数为t0*t1

再讨论直接去对面的情况

假如这个点没有矛盾点且他所在的组织超过1人（要保证每一边至少有一人），则他可以去对面

然后初始解假如每一边都至少有一人，那么这也是一个合法方案

code：

 #include<cstdio>

 #include<iostream>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #define maxn 5005

 using namespace std;

 char ch;

 bool ok;

 void read(int &x){

     for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;

     for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());

     if (ok) x=-x;

 }

 int n,k,x,con[maxn],cnt0,cnt1,list0[maxn],list1[maxn],num[maxn],boom[maxn];

 bool g[maxn][maxn],bo[maxn];

 struct Graph{

     int tot,now[maxn<<],son[maxn*maxn],pre[maxn*maxn];

     int idx,dfn[maxn<<],low[maxn<<],top,stack[maxn],cnt,bel[maxn<<];

     bool in[maxn<<];

     void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}

     void dfs(int u){

         dfn[u]=low[u]=++idx,stack[++top]=u,in[u]=;

         for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])

             if (!dfn[v]) dfs(v),low[u]=min(low[u],low[v]);

             else if (in[v]) low[u]=min(low[u],dfn[v]);

         if (dfn[u]==low[u]){

             int v; ++cnt;

             do{v=stack[top--],in[v]=,bel[v]=cnt;}while (v!=u);

         }

     }

 }G;

 int main(){

     read(n);

     for (int i=;i<=n;i++){

         read(k),con[i]=k;

         while (k--) read(x),g[i][x]=;

     }

     for (int i=;i<=n;i++) for (int j=;j<=n;j++) if (i!=j){

         if (g[i][j]) G.put((i<<)+,j<<); else G.put(i<<,(j<<)+);

     }

     for (int i=;i<=(n<<)+;i++) if (!G.dfn[i]) G.dfs(i);

     for (int i=;i<=n;i++){

         if (G.bel[i<<]==G.bel[(i<<)+]){puts("");return ;}

         if (G.bel[i<<]<G.bel[(i<<)+]) list0[++cnt0]=i;

         else bo[i]=,list1[++cnt1]=i;

     }

     int ans=(cnt0&&cnt1);

     for (int i=;i<=cnt0;i++) for (int j=;j<=cnt1;j++)

         if (g[list0[i]][list1[j]]) num[list0[i]]++,boom[list0[i]]=list1[j];

     for (int i=;i<=cnt1;i++) for (int j=;j<=cnt0;j++)

         if (!g[list1[i]][list0[j]]) num[list1[i]]++,boom[list1[i]]=list0[j];

     for (int i=;i<=n;i++) if (num[i]==){

         if (num[boom[i]]==&&boom[i]>i&&boom[boom[i]]==i) ans++;

         else if (!num[boom[i]]) ans++;

     }

     int t0=,t1=;

     for (int i=;i<=n;i++) if (!num[i]){

         if ((bo[i]&&cnt1>)||(!bo[i]&&cnt0>)) ans++;

         if (bo[i]) t1++; else t0++;

     }

     ans+=t1*t0;

     printf("%d\n",ans);

     return ;

 }

巴特西