bzoj2215: [Poi2011]Conspiracy

本文主要是介绍bzoj2215: [Poi2011]Conspiracy，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2215

思路：一道很好的2-sat题

首先一个人要么分配给同谋者，要么分配给后勤组织

这可以考虑２-sat

那么怎么连边？这个很显然

如果(i,j)有边，那么一个在同谋者，则另一个必不在同谋者

如果(i,j)无边，那么一个在后勤组织，另一个必不在后勤组织

然后考虑求方案数

先求出一种方案

然后我们就会发现一个性质

只会有一个人被换过去，或者换过来

因为两个后勤组织的人一定有边，不可能同时换过去

同理因为两个同谋者的人一定无边，不可能同时换过去

于是就可以愉(keng)快(die)地分类讨论了

首先有三种情况

１：从后勤组织过去一个人

２：从同谋者过去一个人

３：两个组织互换一个人

先预处理出每个人到另一个组织后会有几个人和他冲突，如果只有一个，和他冲突的是谁

对于过去一个人的情况

只要无人与他冲突并且过去后还有人即可方案数＋１

对于交换的情况

１．如果i有一个冲突的人j，那么如果j也只有一个冲突的人并且j冲突的人是i，那么方案数＋１，但为了不重复，只在i<j时统计

２．如果i有一个冲突的人j，j没有冲突的人，那么方案数＋１，这种不会重复

３．如果i没有冲突的人，那么它和另一个团体中任意一个也没有冲突的人可以互换

记录后勤组织交换后无冲突的人数t0，同谋者交换后无冲突的人数t1

方案数+=t1*t2

然后就没有然后了

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=10010,maxm=50000010;
using namespace std;
int n,low[maxn],dfn[maxn],tim,sta[maxn],top,bel[maxn],bcnt,cnt1,cnt0,boom[maxn],ans[maxn];bool g[5010][5010],ins[maxn];
int pre[maxm],now[maxn],son[maxm],tot,cnt[maxn],res;char ch;
int p0(int x){return x<<1;}
int p1(int x){return (x<<1)|1;}
void read(int &x){for (ch=getchar();!isdigit(ch);ch=getchar());for (x=0;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
}
//0是后勤(有边)　1是同谋者(无边)
void add(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
void tarjan(int x){dfn[x]=low[x]=++tim,ins[x]=1,sta[++top]=x;for (int y=now[x];y;y=pre[y]){if (!dfn[son[y]]) tarjan(son[y]),low[x]=min(low[x],low[son[y]]);else if (ins[son[y]]) low[x]=min(low[x],dfn[son[y]]);}if (dfn[x]==low[x]){int xx;bcnt++;do{xx=sta[top--],ins[xx]=0,bel[xx]=bcnt;}while (x!=xx); }
}void init(){scanf("%d",&n);for (int i=1,k;i<=n;i++){read(k);for (int j=1,x;j<=k;j++) read(x),g[i][x]=g[x][i]=1;}//for (int i=1;i<=n;i++,puts("")) for (int j=1;j<=n;j++) printf("%d ",g[i][j]);for (int a=1;a<=n;a++) for (int b=1;b<a;b++){if (g[a][b]) add(p1(a),p0(b)),add(p1(b),p0(a));else add(p0(a),p1(b)),add(p0(b),p1(a));}
}void work(){for (int i=2;i<=p1(n);i++) if (!dfn[i]) tarjan(i);for (int i=1;i<=n;i++) if (bel[p0(i)]==bel[p1(i)]) return;for (int i=1;i<=n;i++){ans[i]=(bel[p0(i)]>bel[p1(i)]);if (ans[i]) cnt1++;else cnt0++;}//for (int i=1;i<=n;i++) printf("%d %d\n",i,ans[i]);//if (!cnt0||!cnt1) return;res=(cnt0&&cnt1);int t0=0,t1=0;for (int i=1;i<=n;i++){if (ans[i]){for (int j=1;j<=n;j++) if (i!=j&&!ans[j]&&!g[i][j])cnt[i]++,boom[i]=j;}else{for (int j=1;j<=n;j++) if (i!=j&&ans[j]&&g[i][j])cnt[i]++,boom[i]=j;}}//for (int i=1;i<=n;i++) printf("%d %d %d %d\n",i,ans[i],cnt[i],boom[i]);for (int i=1;i<=n;i++) if (!ans[i]){if (!cnt[i]&&cnt0>1) res++;if (!cnt[i]) t0++;if (cnt[i]==1)if ((boom[boom[i]]==i&&cnt[boom[i]]==1&&i<boom[i])||!cnt[boom[i]]) res++;}for (int i=1;i<=n;i++) if (ans[i]){if (!cnt[i]&&cnt1>1) res++;if (!cnt[i]) t1++;if (cnt[i]==1)if ((boom[boom[i]]==i&&cnt[boom[i]]==1&&i<boom[i])||!cnt[boom[i]]) res++;}res+=t0*t1;
}int main(){init(),work(),printf("%d\n",res);return 0;
}

这篇关于bzoj2215: [Poi2011]Conspiracy的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---