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

Boleyn Su's Blog

 
 
 
 
 

日志

 
 

[The 2011 ACM-ICPC Asia Chengdu Regional Contest]E.Eliminate the Conflict  

2011-12-03 18:06:59|  分类: 信息学 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
2-SAT。
CODE:
#include <cstring>
using namespace std;
const
int MAXV=20000;
const
int MAXE=1000000;
struct
struct_edge{int v;struct_edge* n;};
typedef
struct_edge* edge;
typedef
void function(int block,int node);
int
V;
struct_edge pool[MAXE];
edge top;
edge adj[MAXV];
void
build_graph()
{

top=pool;
memset(adj,0,sizeof(adj));
//V;
//add_edge(u,v);
}
void
add_edge(int u,int v)
{

top->v=v,top->n=adj[u],adj[u]=top++;
}

int
stamp;
int
DFN[MAXV];
int
LOW[MAXV];
int
st;
int
s[MAXV];
bool
ins[MAXV];
bool
visited[MAXV];
int
depth;
edge e[MAXV];
int
root[MAXV];
int
block;

void
tarjan(function f)
{

memset(visited,0,sizeof(visited));
memset(ins,0,sizeof(ins));
st=0;
block=0;
for
(int start=0;start<V;start++)
if
(!visited[start])
{

depth=0;
root[depth]=start;
e[depth]=adj[root[depth]];
DFN[root[depth]]=LOW[root[depth]]=++stamp;
ins[s[st++]=root[depth]]=true;
visited[root[depth]]=true;
do

{

if
(e[depth])
{

if
(!visited[e[depth]->v])
{

int
depth_=depth+1;
e[depth_]=adj[root[depth_]=e[depth]->v];
DFN[root[depth_]]=LOW[root[depth_]]=++stamp;
ins[s[st++]=root[depth_]]=true;
visited[root[depth_]]=true;
e[depth]=e[depth]->n;
depth++;
}

else if
(ins[e[depth]->v])
{

if
(LOW[root[depth]]>DFN[e[depth]->v])
LOW[root[depth]]=DFN[e[depth]->v];
e[depth]=e[depth]->n;
}

else
e[depth]=e[depth]->n;
}

else

{

if
(LOW[root[depth]]==DFN[root[depth]])
{

do

{

ins[s[--st]]=false;
f(block,s[st]);
}

while
(s[st]!=root[depth]);
block++;
}

if
(depth>0)
{

int
depth_=depth-1;
if
(LOW[root[depth_]]>LOW[root[depth]])
LOW[root[depth_]]=LOW[root[depth]];
}

depth--;
}
}

while
(depth>=0);
}
}


typedef
struct_edge struct_list;
typedef
edge list;
int
block_id[MAXV];
struct_list spool[MAXV];
list stop;
list set[MAXV];
#define T(x) ((x)<<1)
#define F(x) (((x)<<1)|1)
void build_2sat()
{

stop=spool;
memset(set,0,sizeof(set));
build_graph();
//add_edge(u,v);
}
void
function_2sat(int block,int node)
{

block_id[node]=block;
stop->v=node,stop->n=set[node],set[node]=stop++;
}

#include <iostream>
using namespace std;
bool
possible_2sat()
{

tarjan(function_2sat);
for
(int i=0;i<(V>>1);i++)
if
(block_id[T(i)]==block_id[F(i)])
return
false;
return
true;
}


int
N,M;
int
B[MAXV];
int
main()
{

int
T;
cin>>T;
for
(int t=1;t<=T;t++)
{

cin>>N>>M;
V=N*2;
build_2sat();
for
(int i=0;i<N;i++)
cin>>B[i],B[i]--;
for
(int i=0;i<M;i++)
{

int
a,b,k;
cin>>a>>b>>k;
a--,b--;
if
(k)
{

if
(B[a]==B[b])
{

add_edge(T(a),F(b));
add_edge(F(b),T(a));
add_edge(F(a),T(b));
add_edge(T(b),F(a));
}

else if
((B[a]+1)%3==B[b]) add_edge(F(a),F(b));
else
add_edge(F(b),F(a));
}

else

{

if
(B[a]==B[b])
{

add_edge(T(a),T(b));
add_edge(T(b),T(a));
add_edge(F(a),F(b));
add_edge(F(b),F(a));
}

else if
((B[a]+1)%3==B[b])
{

add_edge(F(a),T(b));
add_edge(T(b),F(a));
add_edge(T(a),F(a));
add_edge(F(b),T(b));
}

else

{

add_edge(F(b),T(a));
add_edge(T(a),F(b));
add_edge(T(b),F(b));
add_edge(F(a),T(a));
}
}
}

cout<<"Case #"<<t<<": "<<(possible_2sat()?"yes":"no")<<endl;
}
}
  评论这张
 
阅读(979)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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