BZOJ 2199 [Usaco2011 Jan]奶牛议会

题目大意

每个元素有两个状态，每个人会指定两个元素的指定状态，这两个指定项中必须至少一个是真的，问如何为每个元素选择状态才能使得整体成立，如果能请输出每个元素的状态：是被钦定成为一个状态还是可能是任意一种。

这道题首先一看各种"2"就基本上是2-SAT了。因为数据范围很小（元素数量≤1000）给我们的时间是很多的。所以可以使用朴素2-SAT。

本来还在思考如何一遍朴素2-SAT跑出来后来得知因为元素数量过少可以跑元素数量次= =还有这种操作？

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,ina,inc,s[10010],tops,t[10010],topt,head[10010],tot,nex[10010],to[10010],ans[10010];
char inb[5],ind[5],prians[]="YN?";
bool use[10010];
bool dfs(int pos)
{
	if(use[pos^1]) return false;
	if(use[pos]) return true;
	use[pos]=true;
	s[++tops]=pos;
	for(int i=head[pos];i;i=nex[i])
		if(!dfs(to[i])) return false;
	return true;
}
void addedge(int tx,int ty)
{
	to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%s%d%s",&ina,inb,&inc,ind);
		ina=inb[0]=='Y'?ina*2:ina*2+1;
		inc=ind[0]=='Y'?inc*2:inc*2+1;
		addedge(ina^1,inc);
		addedge(inc^1,ina);
	}
	for(int i=1;i<=n;++i)
	{
		int tx=i<<1,ty=i<<1|1;
		memset(use,false,sizeof use);
		tx=dfs(tx);
		memset(use,false,sizeof use);
		ty=dfs(ty);
		if(!tx&&!ty)
		{
			printf("IMPOSSIBLE\n");
			return 0;
		}
		if(tx&&ty) ans[i]=2;
		else if(ty) ans[i]=1;
	}
	for(int i=1;i<=n;++i)
		printf("%c",prians[ans[i]]);
	printf("\n");
	return 0;
}

我还有0msWA惨剧的代码也发上来吧qwq尝试使用一次2-SAT解决问题但是GG了……

#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,ina,inc,s[1000010],tops,t[1000010],topt,head[1000010],tot,nex[1000010],to[1000010];
char inb[5],ind[5];
bool use[1000010],ans[1000010];
bool dfs(int pos)
{
    if(use[pos^1]) return false;
    if(use[pos]) return true;
    use[pos]=true;
    s[++tops]=pos;
    for(int i=head[pos];i;i=nex[i])
        if(!dfs(to[i])) return false;
    return true;
}
bool solve()
{
    for(int i=1;i<=n;++i)
        if(!use[i<<1]&&!use[i<<1|1])
        {
            tops=0;
            if(!dfs(i<<1))
            {
                while(tops) use[s[tops--]]=false;
                if(!dfs(i<<1|1)) return false;
                else for(int j=1;j<=tops;j++) ans[s[j]]=true;
            }
            else
            {
                topt=tops;
                for(int j=1;j<=tops;++j) t[j]=s[j];
                while(tops) ans[s[tops]]=true,use[s[tops--]]=false;
                if(dfs(i<<1|1)) {for(int j=1;j<=tops;j++) ans[s[j]]=true;}
                else
                {
                    while(tops) use[s[tops--]]=false;
                    for(int j=1;j<=topt;++j) use[t[j]]=true;
                }
            }
        }
    return true;
}
void addedge(int tx,int ty)
{
    to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%s%d%s",&ina,inb,&inc,ind);
        ina=inb[0]=='Y'?ina*2:ina*2+1;
        inc=ind[0]=='Y'?inc*2:inc*2+1;
        addedge(ina^1,inc);
        addedge(inc^1,ina);
    }
    if(!solve()) printf("IMPOSSIBLE\n");
    else
    {
        for(int i=1;i<=n;++i)
        {
            if(ans[i<<1|1]&&ans[i<<1]) {printf("?");continue;}
            if(ans[i<<1]) printf("Y");
            if(ans[i<<1|1]) printf("N");
        }
        printf("\n");
    }
}