poj 3740 Easy Finding 精确匹配

  1 #include <iostream>
  2 #include <vector>
  3 #include <cstdio>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <cmath>
  7 #include <map>
  8 #include <set>
  9 #include <string>
 10 #include <queue>
 11 using namespace std;
 12 #define pb(x) push_back(x)
 13 #define ll long long
 14 #define mk(x, y) make_pair(x, y)
 15 #define lson l, m, rt<<1
 16 #define mem(a) memset(a, 0, sizeof(a))
 17 #define rson m+1, r, rt<<1|1
 18 #define mem1(a) memset(a, -1, sizeof(a))
 19 #define mem2(a) memset(a, 0x3f, sizeof(a))
 20 #define rep(i, a, n) for(int i = a; i<n; i++)
 21 #define ull unsigned long long
 22 typedef pair<int, int> pll;
 23 const double PI = acos(-1.0);
 24 const double eps = 1e-8;
 25 const int mod = 1e9+7;
 26 const int inf = 1061109567;
 27 const int dir[][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
 28 const int maxn = 305;
 29 const int maxNode = 5000;
 30 struct DLX {
 31     int L[maxNode], R[maxNode], U[maxNode], D[maxNode], row[maxNode], col[maxNode];
 32     int S[maxn], H[maxn], deep, ans[maxn], sz, n, m;
 33     void remove(int c) {
 34         L[R[c]] = L[c] ;
 35         R[L[c]] = R[c] ;
 36         for(int i = D[c]; i!=c; i = D[i])
 37             for(int j = R[i]; j!=i; j = R[j]) {
 38                 U[D[j]] = U[j] ;
 39                 D[U[j]] = D[j] ;
 40                 S[col[j]]--;
 41             }
 42     }
 43     void resume(int c) {
 44         for(int i = U[c]; i!=c; i = U[i])
 45             for(int j = L[i]; j!=i; j = L[j]) {
 46                 S[col[j]]++;
 47                 D[U[j]] = j;
 48                 U[D[j]] = j;
 49             }
 50         R[L[c]] = c;
 51         L[R[c]] = c;
 52     }
 53     int dfs(int d) {
 54         if(R[0] == 0) {
 55             deep = d;
 56             return 1;
 57         }
 58         int c = R[0];
 59         for(int i = R[0]; i!=0; i = R[i])
 60             if(S[c]>S[i])
 61                 c = i;
 62         remove(c);
 63         for(int i = D[c]; i!=c; i = D[i]) {
 64             ans[d] = row[i];
 65             for(int j = R[i]; j!=i; j = R[j])
 66                 remove(col[j]);
 67             if(dfs(d+1))
 68                 return 1;
 69             for(int j = L[i]; j!=i; j = L[j])
 70                 resume(col[j]);
 71         }
 72         resume(c);
 73         return 0;
 74     }
 75     void add(int r, int c) {
 76         sz++;
 77         row[sz] = r;
 78         col[sz] = c;
 79         S[c]++;
 80         U[sz] = U[c];
 81         D[sz] = c;
 82         D[U[c]] = sz;
 83         U[c] = sz;
 84         if(~H[r]) {
 85             R[sz] = H[r];
 86             L[sz] = L[H[r]];
 87             L[R[sz]] = sz;
 88             R[L[sz]] = sz;
 89         } else {
 90             H[r] = L[sz] = R[sz] = sz;
 91         }
 92     }
 93     void init(){
 94         mem1(H);
 95         for(int i = 0; i<=n; i++) {
 96             R[i] = i+1;
 97             L[i] = i-1;
 98             U[i] = i;
 99             D[i] = i;
100         }
101         R[n] = 0;
102         L[0] = n;
103         sz = n;
104     }
105     void solve () {
106         init() ;
107         for(int i = 1; i<=m; i++) {
108             for(int j = 1; j<=n; j++) {
109                 int x;
110                 scanf("%d", &x);
111                 if(x) {
112                     add(i, j);
113                 }
114             }
115         }
116         if(dfs(0)) {
117             printf("Yes, I found it\n");
118         } else {
119             printf("It is impossible\n");
120         }
121     }
122 }dlx;
123 int main()
124 {
125     while(~scanf("%d%d", &dlx.m, &dlx.n)) {
126         dlx.solve();
127     }
128     return 0;
129 }