uva 10319(2-SAT)

题意:在一个长方形网格中有行(street)和列(avenue)。然后每两个点(x,y)之间有一条简单路径表示他们只要转一次弯。每各行和列都是单向的方向由你来决定。问你能不能满足所有给你的询问(a, b)都有一条a->b的简单路径。

思路:我们可以看到一共有m+n条路每条路都有两个方向可以选。这样就联想到了2-sat,然后就是分析题目

 

uva 10319(2-SAT)

对于两个点当横坐标和纵坐标都不想等的时候我们会得到上面这种情况。(a^b)U(c^d) = (a U d)^(b U c)^(a U c)^(b U d)

对于横坐标纵坐标都想等我们不需要建边。然而有一个相等,若是a = 非a->a而非a = a->非a。

图建完后套模版就是了。

代码如下:

uva 10319(2-SAT)
  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-01-29 19:07
  5  * Filename     : uva_10319.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <algorithm>
 15 #include <queue>
 16 #include <stack>
 17 #include <vector>
 18 #include <set>
 19 #include <map>
 20 #define MP(a, b) make_pair(a, b)
 21 #define PB(a) push_back(a)
 22 
 23 using namespace std;
 24 typedef long long ll;
 25 typedef pair<int, int> pii;
 26 typedef pair<unsigned int,unsigned int> puu;
 27 typedef pair<int, double> pid;
 28 typedef pair<ll, int> pli;
 29 typedef pair<int, ll> pil;
 30 
 31 const int INF = 0x3f3f3f3f;
 32 const double eps = 1E-6;
 33 const int LEN =10010;
 34 const int ROW = 0;
 35 const int COL = 1;
 36 vector<int> Map[LEN], rMap[LEN], vs;
 37 int n, m, vis[LEN], cmp[LEN];
 38 
 39 //pos | col or row | true or false
 40 int ch(int pos, int f, int isf){
 41     return pos*2 + f*n*2 + isf;
 42 }
 43 
 44 void dfs(int v){
 45     vis[v] = 1;
 46     for(int i=0; i<Map[v].size(); i++)
 47         if(!vis[Map[v][i]]) dfs(Map[v][i]);
 48     vs.PB(v);
 49 }
 50 
 51 void rdfs(int v, int f){
 52     vis[v] = 1;
 53     cmp[v] = f;
 54     for(int i=0; i<rMap[v].size(); i++)
 55         if(!vis[rMap[v][i]]) rdfs(rMap[v][i], f);
 56 }
 57 
 58 int scc()
 59 {
 60     memset(vis, 0, sizeof vis);
 61     vs.clear();
 62     for(int i=0; i<2*(n+m); i++)if(!vis[i])dfs(i);
 63     memset(vis, 0, sizeof vis);    
 64     int f = 0;
 65     for(int i=vs.size()-1; i>=0; i--)if(!vis[vs[i]])rdfs(vs[i], f++);
 66     return f;
 67 }
 68 
 69 bool Judge(){
 70     scc();
 71     for(int i=0; i<2*(n+m); i+=2)
 72         if(cmp[i] == cmp[i+1]) return false;
 73     return true;
 74 }
 75 
 76 // a U b
 77 void add(int a, int b){
 78      Map[a^1].PB(b);
 79      Map[b^1].PB(a);
 80      rMap[b].PB(a^1);
 81      rMap[a].PB(b^1);
 82 }
 83 
 84 void addedge(int a, int b, int c, int d)
 85 {
 86     if(a == c && b == d) return ;
 87     if(a != c && b != d){    // (a U d)^(b U c)^(a U c)^(b U d)
 88         int _a = ch(a, ROW, d-b>0?0:1);
 89         int _b = ch(b, COL, c-a>0?0:1);
 90         int _c = ch(c, ROW, d-b>0?0:1);
 91         int _d = ch(d, COL, c-a>0?0:1);
 92         add(_a, _b);
 93         add(_c, _d);
 94         add(_a, _c);
 95         add(_b, _d);
 96     }else{
 97         if(a == c && d-b > 0){
 98             Map[ch(a, ROW, 1)].PB(ch(a, ROW, 0));
 99             rMap[ch(a, ROW, 0)].PB(ch(a, ROW, 1));
100         }    
101         if(a == c && d-b < 0){
102             Map[ch(a, ROW, 0)].PB(ch(a, ROW, 1));
103               rMap[ch(a, ROW, 1)].PB(ch(a, ROW, 0));
104         }
105         if(b == d && c-a > 0){
106             Map[ch(b, COL, 1)].PB(ch(b, COL, 0));
107             rMap[ch(b, COL, 0)].PB(ch(b, COL, 1));    
108         }    
109         if(b == d && c-a < 0){
110             Map[ch(b, COL, 0)].PB(ch(b, COL, 1));
111             rMap[ch(b, COL, 1)].PB(ch(b, COL, 0));    
112         }    
113     }
114 }
115 
116 int main()
117 {
118 //    freopen("in.txt", "r", stdin);
119 
120     int T, q, a, b, c, d;
121     scanf("%d", &T);
122     while(T--){
123         for(int i=0; i<LEN; i++)Map[i].clear();
124         for(int i=0; i<LEN; i++)rMap[i].clear();
125         scanf("%d%d%d", &n, &m, &q);
126         for(int i=0; i<q; i++){
127             scanf("%d%d%d%d", &a, &b, &c, &d);
128             addedge(a-1, b-1, c-1, d-1);
129         }
130         if(Judge()) printf("Yes\n");
131         else printf("No\n");
132     }
133     return 0;
134 }
View Code

uva 10319(2-SAT)

上一篇:leetcode--Valid Sudoku


下一篇:【语法】NSMutableString的用法