poj3678

题目给的太裸,显然2sat;

还是用i表示xi=true(1), i+n表示xi=false(0)

这题唯一要说的是一种情况,当xi必须=true或xi必须=false这种情况下怎么弄

比如这道题出现的 假如条件要求xi or xj=0 那么

除了i+n--->j+n ,j+n--->i+n这两条边外

显然还要xi,xj都必须取false

这种情况我们好像不好用“推导出”的原理建边,

考虑这样的情况1,假如存在路径i+n--->i,但不存在路径i--->i+n

为什么这种情况是有解的,这是因为我们我们可以取i这个状态,这样就成立了,而取i+n这个状态是不成立的

现在我们要求一定只能取i+n这个状态

我们就连边i--->i+n

假如是情况1,加上这条边后,显然无解,符合。

假如i和i+n间都没有路径,显然加了这条边之后,就转化为情况1,这样显然只能取i+n这个状态

假如原来无解,加了边之后现在当然也无解

所以,对于xi,not xi,我们一定要取xi的话

我们就连边xi<--- not xi,这样就可以了

 type node=record
       next,point:longint;
     end; var edge:array[..] of node;
    v,f:array[..] of boolean;
    be,st,dfn,low,p:array[..] of longint;
    sum,h,t,a,b,c,i,n,m,len:longint;
    s:string; function min(a,b:longint):longint;
  begin
    if a>b then exit(b) else exit(a);
  end; procedure add(x,y:longint);
  begin
    inc(len);
    edge[len].point:=y;
    edge[len].next:=p[x];
    p[x]:=len;
  end; procedure tarjan(x:longint);
  var i,y:longint;
  begin
    inc(h);
    dfn[x]:=h;
    low[x]:=h;
    inc(t);
    st[t]:=x;
    f[x]:=true;
    v[x]:=true;
    i:=p[x];
    while i<>- do
    begin
      y:=edge[i].point;
      if not v[y] then
      begin
        tarjan(y);
        low[x]:=min(low[x],low[y]);
      end
      else if f[y] then low[x]:=min(low[x],low[y]);
      i:=edge[i].next;
    end;
    if dfn[x]=low[x] then
    begin
      inc(sum);
      while st[t+]<>x do
      begin
        y:=st[t];
        f[y]:=false;
        be[y]:=sum;
        dec(t);
      end;
    end;
  end; begin
  fillchar(p,sizeof(p),);
  readln(n,m);
  for i:= to m do
  begin
    read(a,b,c);
    inc(a);
    inc(b);
    readln(s);
    if s=' AND' then
    begin
      if c= then
      begin
        add(a,b+n);
        add(b,a+n);
      end
      else begin
        add(a,b);
        add(b,a);
        add(a+n,a);
        add(b+n,b);
      end;
    end
    else if s=' OR' then
    begin
      if c= then
      begin
        add(a+n,b+n);
        add(b+n,a+n);
        add(a,a+n);
        add(b,b+n);
      end
      else begin
        add(a+n,b);
        add(b+n,a);
      end;
    end
    else if s=' XOR' then
    begin
      if c= then
      begin
        add(a+n,b+n);
        add(b+n,a+n);
        add(a,b);
        add(b,a);
      end
      else begin
        add(a+n,b);
        add(a,b+n);
        add(b+n,a);
        add(b,a+n);
      end;
    end;
  end;
  for i:= to *n do
    if not v[i] then
    begin
      h:=;
      t:=;
      tarjan(i);
    end;   for i:= to n do
    if be[i]=be[i+n] then
    begin
      writeln('NO');
      halt;
    end;
  writeln('YES');
end.
上一篇:JavaScript平常会跳的坑系列(一)


下一篇:Spring Struts2 整合