NWERC 2012 Problem I Idol

又是个2-sat的模板题;

反正评委的选择必须有一个是正确的,1错误,那么2就必须正确;

这就是一个2-sat问题。

直接上白书的模板啊,不过稍微要注意的一点是对于第一个点必须要选择,不然就违反了题意;

代码:

 #include<cstdio>
#define maxn 2005
#define maxm 4005
#include<vector>
#include<cstring>
using namespace std;
struct twosat
{
int n;
vector<int>g[maxn*];
bool mark[maxn*];
int s[maxn*],c; bool dfs(int x)
{
if(mark[x^])return ;
if(mark[x])return ;
mark[x]=;
s[c++]=x;
for(int i=; i<g[x].size(); i++)
if(!dfs(g[x][i]))return ;
return ;
}
void init(int n)
{
this->n=n;
for(int i=; i<*n; i++)g[i].clear();
memset(mark,,sizeof mark);
}
void add_clase(int x,int y)
{
g[x].push_back(y);
}
bool solve()
{
mark[]=,mark[]=;//强制让1选上去;
for(int i=; i<n*; i+=)
if(!mark[i]&&!mark[i+])
{
c=;
if(!dfs(i))
{
while(c>)mark[s[--c]]=;
if(!dfs(i+))return ;
}
}
return ;
}
} getans; int main()
{
int n,m,u,v;
while(scanf("%d%d",&n,&m)!=EOF)
{
getans.init(n);
for(int i=; i<m; i++)
{
scanf("%d%d",&u,&v);
if (u<) {u++;u=(-u)<<;}
else {u--;u=u<<|;}
if (v<) {v++;v=(-v)<<;}
else {v--;v=v<<|;}
getans.add_clase(u^,v);
getans.add_clase(v^,u);
}
if(getans.solve())puts("yes");
else puts("no");
}
return ;
}
上一篇:Zepto picLazyLoad Plugin,图片懒加载的Zepto插件


下一篇:Linux 单用户模式的使用