bzoj 2199: [Usaco2011 Jan]奶牛议会（2-SAT+拓扑序+bitset）

2019-11-08 01:30:22

字体：大中小

来源：转载

供稿：网友

2199: [Usaco2011 Jan]奶牛议会

Time Limit: 10 Sec Memory Limit: 259 MBSubmit: 360 Solved: 229[Submit][Status][Discuss]

Description

由于对Farmer John的领导感到极其不悦，奶牛们退出了农场，组建了奶牛议会。议会以“每头牛都可以获得自己想要的”为原则，建立了下面的投票系统： M只到场的奶牛 (1 <= M <= 4000) 会给N个议案投票(1 <= N <= 1,000) 。每只奶牛会对恰好两个议案 B_i and C_i (1 <= B_i <= N; 1 <= C_i <= N)投出“是”或“否”（输入文件中的'Y'和'N'）。他们的投票结果分别为VB_i (VB_i in {'Y', 'N'}) and VC_i (VC_i in {'Y', 'N'})。最后，议案会以如下的方式决定：每只奶牛投出的两票中至少有一票和最终结果相符合。例如Bessie给议案1投了赞成'Y'，给议案2投了反对'N'，那么在任何合法的议案通过方案中，必须满足议案1必须是'Y'或者议案2必须是'N'（或者同时满足）。给出每只奶牛的投票，你的工作是确定哪些议案可以通过，哪些不能。如果不存在这样一个方案，输出"IMPOSSIBLE"。如果至少有一个解，输出： Y 如果在每个解中，这个议案都必须通过 N 如果在每个解中，这个议案都必须驳回 ? 如果有的解这个议案可以通过，有的解中这个议案会被驳回考虑如下的投票集合： - - - - - 议案 - - - - - 1 2 3 奶牛 1 YES NO 奶牛 2 NO NO 奶牛 3 YES YES 奶牛 4 YES YES 下面是两个可能的解： * 议案 1 通过（满足奶牛1，3，4） * 议案 2 驳回（满足奶牛2） * 议案 3 可以通过也可以驳回（这就是有两个解的原因）事实上，上面的问题也只有两个解。所以，输出的答案如下： YN?

Input

* 第1行：两个空格隔开的整数：N和M * 第2到M+1行：第i+1行描述第i只奶牛的投票方案：B_i, VB_i, C_i, VC_i

Output

* 第1行：一个含有N个字符的串，第i个字符要么是'Y'（第i个议案必须通过），或者是'N' （第i个议案必须驳回），或者是'?'。如果无解，输出"IMPOSSIBLE"。

Sample Input

3 41 Y 2 N1 N 2 N1 Y 3 Y1 Y 2 Y

Sample Output

YN?

HINT

Source

Gold

[Submit][Status][Discuss]

题解：2-SAT+拓扑序+bitset

x表选Y，x'表示选N

对于每一个投票方案： x'->y ,y'->x

然后用tarjan缩点，判断是否存在可行解。

如果存在可行解，对于缩点后的图用拓扑序求出每个点有哪些点能到达他。

如果x->x'，那么一定只能选N

如果x'->x，那么一定只能选Y

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#include<bitset>#include<queue>#define N 100003using namespace std;int n,m,tot,tt;int point[N],v[N],nxt[N],cnt,sz,top;int head[N],u[N],next[N];int st[N],belong[N],ins[N],low[N],dfsn[N],vis[N];bitset<2003> mp[2003],mp1[2003];void add(int x,int y){	tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;//	cout<<x<<" "<<y<<endl;}void build(int x,int y){	tt++; next[tt]=head[x]; head[x]=tt; u[tt]=y;	//cout<<x<<" "<<y<<endl;}void tarjan(int x){	st[++top]=x; ins[x]=1; low[x]=dfsn[x]=++sz;	for (int i=point[x];i;i=nxt[i]) {		int j=v[i];		if (!dfsn[j]) tarjan(j),low[x]=min(low[x],low[j]);		else if (ins[j]) low[x]=min(low[x],dfsn[j]);	}    if (low[x]==dfsn[x]) {    	int j; ++cnt;    	do{    		j=st[top--];    		belong[j]=cnt;    		ins[j]=0;		}while (j!=x);	}}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	scanf("%d%d",&n,&m);	for (int i=1;i<=m;i++) {		int x,y,xx,yy; char s[10],s1[10];		scanf("%d%s%d%s",&x,&s,&y,&s1);		if (s[0]=='Y') xx=x+n;		else xx=x,x=x+n;		if (s1[0]=='Y') yy=y+n;		else yy=y,y=y+n;		add(xx,y); add(yy,x);	}	for (int i=1;i<=2*n;i++) 	 if (!dfsn[i]) tarjan(i);	for (int i=1;i<=n;i++)	 if (belong[i]==belong[i+n]) {	 	PRintf("IMPOSSIBLE/n");	 	return 0;	 }	memset(ins,0,sizeof(ins));	for (int i=1;i<=2*n;i++) 	 for (int j=point[i];j;j=nxt[j]) {	 	int r1=belong[i]; int r2=belong[v[j]];	 	if (r1!=r2) {	 		ins[r2]++;	 		build(r1,r2);		 }	 }	//for (int i=1;i<=2*n;i++) cout<<belong[i]<<" ";//	cout<<endl;	for (int i=1;i<=2*n;i++) 	 mp[belong[i]][i]=1;	for (int i=1;i<=cnt;i++) mp1[i]=mp[i];	queue<int> p;	for (int i=1;i<=2*n;i++) if (!ins[i]) p.push(i);	while (!p.empty()) {		int now=p.front(); p.pop();		for (int i=head[now];i;i=next[i]){			mp[u[i]]|=mp[now];			ins[u[i]]--;			if (!ins[u[i]]) p.push(u[i]);		}	}	memset(vis,-1,sizeof(vis));/*	for (int i=1;i<=cnt;i++) {		for (int j=1;j<=2*n;j++) cout<<mp[i][j];		cout<<endl;	}*/	for (int i=1;i<=cnt;i++) {		for (int j=1;j<=n;j++){		 if (mp1[i][j]&&mp[i][j+n]) vis[j]=1;		 else if (mp1[i][j+n]&&mp[i][j]) vis[j]=0;	    } 	} 	for (int i=1;i<=n;i++) 	 if (vis[i]==1) printf("Y"); 	 else if (vis[i]==0) printf("N"); 	 else printf("?"); 	printf("/n");}

上一篇：Cogs 12. 运输问题2(有上下界的有源汇最大流)

下一篇：JS：Drop It！抛弃数组