POI2011 同谋者 Conspiracy
题意
(Bitotia)偷袭了(Byteotia)并占领了很大一块领地。(Byteotia)国王(Byteasar)正在被占领的领地内组织人们抵抗运动。国王需要选择一部分人来作为这场运动的核心。他们会被分成两部分：一部分人作为同谋者在领地内指挥，另一部分人作为后勤提供援助。这两部分人需要满足以下条件：
- 后勤组必须两两认识，确保整个组有效率地合作；
- 同谋者必须两两不认识；
- 至少有一个人作为后勤，一个人作为同谋者。
国王希望知道有多少种方案将人们分成两组，以及是否有可能这样分组。
题解
简单题意就是将一个图划分成一个团和一个独立集的方案数。直接计算似乎不可取，我们考虑当前已知一种方案，通过调整两个集合中的人转移到另一种方案。我们记团的集合为(S)，独立集的集合为(T)，考虑实际上只有三种转移的方式：
- (S)中的一个人被分到(T)中
- (T)中的一个人被分到(S)中
- (S)中的一个人和(T)中的一个人交换
并且容易证明不可能同时有两个人从一个集合分到另一个集合中去。所以我们只要搜出一种答案，那么其余的答案都可以通过这种调整方法得到。搜一个答案是比较简单的，用2-set暴力建图跑(Tarjan)就可以了。然后我们考虑方案数的计算，我们记矛盾值(c_i)表示对于一个点，如果被分到另一个集合中，会有多少个点与之冲突。冲突定义为两点在同在(T)中且有边相连，或同在(S)中且无边相连。如果矛盾值大于(0)，那么我们记(v_i)表示(i)这个点的任意一个矛盾点。
那么对于第一、二中调整方案，显然只有一个集合中的点数大于1且被分配到另一个集合的点矛盾值为0。对于第三种调整方案，我们记需要交换的点为(a,b(u in S,v in T))，那么当(a,b)的矛盾值都为(0)时，显然可以直接交换，当(a,b)某一个点的矛盾值为(1)时（假设为(a)），那么(v_a)则必须为(b)时，两者才可能交换，此时，如果(c_b=0)，或者(c_b=1)并且(v_b=a)时，两者可以交换。容易发现当(c_a>1)或者(c_b>1)时，两者不能交换。然后暴力计算即可，注意不要重复算贡献。
Code
#include<bits/stdc++.h>
using namespace std;
const int N=10005;
int n,tot,clck,tp,bl,c1,c2;
int lk[N],head[N],low[N],dfn[N],ins[N],st[N],block[N],c[N],is[N];
bool vis[N/2][N/2],Mp[N/2][N/2];
vector<int>T,D;
struct edge {
int to,nxt;
}E[25000050];
void Addedge(int u,int v) {
E[++tot].to=v;E[tot].nxt=head[u];head[u]=tot;
}
void Tarjan(int o,int fa) {
dfn[o]=low[o]=++clck;ins[o]=1;
st[++tp]=o;
for(int i=head[o];~i;i=E[i].nxt) {
int to=E[i].to;
if(!dfn[to]) {
Tarjan(to,o);
low[o]=min(low[o],low[to]);
}
else if(ins[to]) low[o]=min(low[o],dfn[to]);
}
if(dfn[o]==low[o]) {
++bl;
while(tp) {
int x=st[tp];--tp;
ins[x]=0;
block[x]=bl;
if(x==o) break;
}
}
}
int main() {
memset(head,-1,sizeof head);
scanf("%d",&n);
for(int i=1,k;i<=n;i++) {
scanf("%d",&k);
for(int j=1,x;j<=k;j++) {
scanf("%d",&x);
lk[x]=1;
Mp[i][x]=Mp[x][i]=1;
}
for(int j=1;j<=n;j++) {
if(i==j) continue;
if(lk[j]) {
Addedge(i+n,j);
}
else {
Addedge(i,j+n);
}
lk[j]=0;
}
}
for(int i=1;i<=n*2;i++) {
if(!dfn[i]) Tarjan(i,-1);
}
for(int i=1;i<=n;i++) {
if(block[i]==block[i+n]) return puts("0"),0;
if(block[i]<block[i+n]) T.push_back(i);
else D.push_back(i);
}
for(int i=0;i<(int)T.size();i++) {
for(int j=0;j<(int)D.size();j++) {
if(Mp[T[i]][D[j]]) {
c[T[i]]++;
if(!is[T[i]]) is[T[i]]=D[j];
}
else {
c[D[j]]++;
if(!is[D[j]]) is[D[j]]=T[i];
}
}
}
for(int i=0;i<(int)T.size();i++) if(!c[T[i]]) c1++;
for(int i=0;i<(int)D.size();i++) if(!c[D[i]]) c2++;
int ans=(T.size()>=1&&D.size()>=1);
ans+=c1*c2;
for(int i=0;i<(int)T.size();i++) {
if(c[T[i]]!=1) continue;
int Ano=is[T[i]];
if(vis[T[i]][Ano]) continue;
if(!c[Ano]) {
vis[T[i]][Ano]=vis[Ano][T[i]];
ans++;
}
else if(c[Ano]==1&&is[Ano]==T[i]) {
vis[T[i]][Ano]=vis[Ano][T[i]];
ans++;
}
}
for(int i=0;i<(int)D.size();i++) {
if(c[D[i]]!=1) continue;
int Ano=is[D[i]];
if(vis[D[i]][Ano]) continue;
if(!c[Ano]) {
vis[D[i]][Ano]=vis[Ano][D[i]];
ans++;
}
else if(c[Ano]==1&&is[Ano]==D[i]) {
vis[D[i]][Ano]=vis[Ano][D[i]];
ans++;
}
}
if(T.size()>1) {
for(int i=0;i<(int)T.size();i++) {
if(!c[T[i]]) ans++;
}
}
if(D.size()>1) {
for(int i=0;i<(int)D.size();i++) {
if(!c[D[i]]) ans++;
}
}
printf("%d
",ans);
return 0;
}