注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

JSOI2010 满汉全席 2-sat水题  

2012-08-23 17:28:21|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
很水很水的2-sat,调了我一个下午
最终还是tarjan写错了,instack数组中忘了把u也清零
细节错误啊,以后再也不敢手写Tarjan了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int MAX=6000+10;

int n,m,begin[MAX],next[MAX*2],t[MAX*2],tot;

int D(int a)
{
return a<=n?a+n:a-n;
}

void addedge(int x,int y)
{
t[++tot]=y;
next[tot]=begin[x];
begin[x]=tot;
}

int dfn[MAX],low[MAX],instack[MAX],st[MAX],fa[MAX],lab;

int findfather(int u)
{
return u==fa[u]?u:fa[u]=findfather(fa[u]);
}

void dfs(int u)
{
low[u]=dfn[u]=++lab;
st[++st[0]]=u;instack[u]=1;
int i,v;
for(i=begin[u];i;i=next[i])
{
v=t[i];
if(!dfn[v])
{
dfs(v);
low[u]=min(low[v],low[u]);
}else if(instack[v])
low[u]=min(dfn[v],low[u]);
}
if(low[u]==dfn[u])
{
while(st[st[0]]!=u && st[0])
{
fa[st[st[0]]]=u;
instack[st[st[0]]]=0;
--st[0];
}
instack[st[st[0]]]=0;
--st[0];
}
}

void work(int T)
{
memset(dfn,0,sizeof dfn);
memset(begin,0,sizeof begin);
memset(instack,0,sizeof instack);
tot=lab=0;
scanf("%d %d",&n,&m);
char Q1[100],Q2[100];
int i,k1,k2,b1,b2;
for(i=1;i<=m;++i)
{
scanf("%s%s",Q1,Q2);
k1=(Q1[0]=='h')?0:1;
k2=(Q2[0]=='h')?0:1;
sscanf(Q1+1,"%d",&b1);sscanf(Q2+1,"%d",&b2);
if(k1)b1+=n;if(k2)b2+=n;
addedge(D(b1),b2);
addedge(D(b2),b1);
}
for(i=1;i<=n+n;++i)
fa[i]=i;
for(i=1;i<=n+n;++i)
if(!dfn[i])
dfs(i);
for(i=1;i<=n;++i)
if(findfather(i)==findfather(i+n))
{
printf("BAD\n");
return;
}
printf("GOOD\n");
return;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int T;
scanf("%d",&T);
for(int i=1;i<=T;++i)
work(i);
}



  评论这张
 
阅读(185)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018