[2-SAT] Codeforces 668E #348 (VK Cup 2016 Round 2, Div. 1 Edition) E. Little Artem and 2-SAT

Advertisement

题解

  Let’s build for both 2-SAT formulas implication graph and let’s find strong connected components in this graph. If both of the formulas are not satisfiable then the answer is SIMILAR. If only one formula is not satisfiable then we can find an answer for the second one and output it.
 Now, let’s assume both formulas are satisfiable. Let’s have a transitive closure for both of the graphs. Let’s call the variable X fixed in the formula F if there is a path -> x or (x -> ). If there is a fixed variable in one formula, but not fixed in the other (or fixed but has other value) we can find the solution for that second formula with opposite value of that fixed variable — that will be an answer. If we could not find these variables, we can remove all of them. There is no fixed variables in the rest of them. Let’s find an edge u->v, presented in one graph, but not presented in the other. Let’s find the solution for formula without the edge with u = 1 and v = 0 (we always can find it). That is the answer.

大概意思就是说
我们先看 f 和 g 是不是都有解 不是的话就输出
然后再考虑 f 和 g 确定值的变量的集合S是不是相同的 不是的话也有解
然后删去 S 的所有变量 再看 f 是不是有路径 u−v 而 g 没有 那么也能构造出 u 和 反v 的解
否则就输出SIMILAR

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<bitset>
using namespace std;

const int N=2005;

struct SAT{
  int n,m,sol;
  int c[N];
  bitset<N> g[N];
  void read(int _n,int _m){
    int iu,iv;
    n=_n; m=_m;
    for (int i=1;i<=m;i++){
      scanf("%d%d",&iu,&iv);
      if (iu>0) iu=(iu-1)<<1|1; else iu=(-iu-1)<<1;
      if (iv>0) iv=(iv-1)<<1|1; else iv=(-iv-1)<<1;
      g[iu^1][iv]=g[iv^1][iu]=1;
    }
    for (int i=0;i<(n<<1);i++) g[i][i]=1;
    for (int k=0;k<(n<<1);k++)
      for (int i=0;i<(n<<1);i++)
    if (g[i][k])
      g[i]|=g[k];
    sol=1;
    for (int i=0;i<(n<<1);i++)
      if (g[i][i^1] && g[i^1][i])
    sol=0;
    if (sol){
      for (int i=0;i<(n<<1);i++) c[i]=-1;
      for (int i=0;i<(n<<1);i++)
    if (g[i][i^1])
      color(i^1);
    }
  }
  void color(int u){
    if (~c[u]) return;
    c[u]=1; c[u^1]=0;
    for (int v=0;v<(n<<1);v++)
      if (g[u][v])
    color(v);
  }
  void solve(int c1=-1,int c2=-1){
    if (~c1) color(c1);
    if (~c2) color(c2);
    for (int i=0;i<(n<<1);i++) if (c[i]==-1) color(i);
    for (int i=0;i<n;i++)
      c[i<<1]?printf("0 "):printf("1 ");
  }
}f,g;

int n,m1,m2;

inline bool Solve(SAT &f,SAT &g){
  if (!f.sol) return 0;
  if (!g.sol)
    return f.solve(),1;
  for (int i=0;i<(n<<1);i++)
    if (f.c[i]!=0 && g.c[i]==0)
      return f.solve(i),1;
  for (int i=0;i<(n<<1);i++)
    if (f.c[i]==-1)
    for (int j=0;j<(n<<1);j++)
      if (f.c[j]==-1)
    if (!f.g[i][j] && g.g[i][j])
      return f.solve(i,j^1),1;
  return 0;
}

int main(){
  freopen("t.in","r",stdin);
  freopen("t.out","w",stdout);
  scanf("%d%d%d",&n,&m1,&m2);
  f.read(n,m1); g.read(n,m2);
  if (!Solve(f,g) && !Solve(g,f))
    printf("SIMILAR\n");
  return 0;
}

Similar Posts:

  • Codeforces Round #348 (VK Cup 2016 Round 2, Div. 2 Edition) B

    B. Little Artem and Grasshopper time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Little Artem found a grasshopper. He brought it to his house and constructed a jumping area for him. The are

  • Codeforces Round #351 (VK Cup 2016 Round 3, Div. 2 Edition) C. Bear and Colors 暴力

    C. Bear and Colors 题目连接: http://www.codeforces.com/contest/673/problem/C Description Bear Limak has n colored balls, arranged in one long row. Balls are numbered 1 through n, from left to right. There are n possible colors, also numbered 1 through n.

  • Codeforces Round #351 (VK Cup 2016 Round 3, Div. 2 Edition) D

    D. Bear and Two Paths time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Bearland has n cities, numbered 1 through n. Cities are connected via bidirectional roads. Each road connects two dist

  • Codeforces Round #351 (VK Cup 2016 Round 3, Div. 2 Edition) A

    A. Bear and Game time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output Bear Limak likes watching sports on TV. He is going to watch a game today. The game lasts 90 minutes and there are no break

  • VK Cup 2016 - Round 1 (Div. 2 Edition) C. Bear and Forgotten Tree 3 构造

    C. Bear and Forgotten Tree 3 题目连接: http://www.codeforces.com/contest/658/problem/C Description A tree is a connected undirected graph consisting of n vertices and n  -  1 edges. Vertices are numbered 1 through n. Limak is a little polar bear and Rade

  • Codeforces Round VK Cup 2015 - Round 1 (unofficial online mirror, Div. 1 only)E. The Art of Dealing with ATM 暴力出奇迹!

    VK Cup 2015 - Round 1 (unofficial online mirror, Div. 1 only)E. The Art of Dealing with ATM Time Limit: 2 Sec Memory Limit: 256 MB Submit: xxx Solved: 2xx 题目连接 http://codeforces.com/contest/529/problem/E Description ATMs of a well-known bank of a sma

  • VK Cup 2016 - Qualification Round 1 (Russian-Speaking Only, for VK Cup teams) A. Voting for Photos 水题

    A. Voting for Photos 题目连接: http://www.codeforces.com/contest/637/problem/A Description After celebrating the midcourse the students of one of the faculties of the Berland State University decided to conduct a vote for the best photo. They published t

  • VK Cup 2015 - Round 1 -E. Rooks and Rectangles 线段树最值+扫描线

    题意: n * m的棋盘, k个位置有"rook"(车),q次询问,问是否询问的方块内是否每一行都有一个车或者每一列都有一个车? 满足一个即可 先考虑第一种情况, 第二种类似,swap一下就可以了. #include <bits/stdc++.h> using namespace std; const int maxn = 1e5 + 5; inline int GetIdx(int l, int r){ return l + r | l != r; } int seg[m

  • [VK Cup 2015 - Round 1]简要题解

    在写这篇题解之前,首先orz学军两位屠场的神犇jcvb和jiry!!!!!!orzzzzzzzzzzzzz B. Group Photo 2 (online mirror version) 题目大意 给你n个矩形,以及它们的w(长).h(宽),它们以它们的长为底边并排紧紧挨在一起,下边缘呈一条直线,你可以将其中不超过[n2]个矩形旋转90度,求最小的覆盖所有矩形的矩形面积是多少. 题解 因为题目范围非常小,wi,hi<=1000,因此最终的最小覆盖矩形的高也肯定不会超过1000,因此可以直接爆枚

  • VK Cup 2012 Round 1

    周六下午战了一下这场的 virtual,过程大致如下: A 上来脑残错 WA 一发,之后改过:D 看到是个大裸题,不过上来看成了 <=K 的个数,我想这不是树分治+树状数组(sb),粘了个树分治模板后发现度错题了(没粘原题的我感觉已经很良心了)..想改成 nlgn 的,不过看 K 那么小,直接 nlgnK 搞了 1Y..其实改了的话也就两三行的事儿,而实际上树形 DP 也是可以随便做的..:然后看 B,发现很简单就做了,中途因为一度不知道该怎么写这个题犹豫了一会儿(sb)..然后 1Y:然后看

Tags: