POJ 2724 - Purifying Machine

http://poj.org/problem?id=2724

概要

2^N 個のチーズがあり，それぞれ二進数で 00...0, ..., 11...1 と番号が割り当てられている． そのうち，与えられた M 個のパターンにマッチするようなチーズがウイルスに感染している． 同様のパターンを用いて浄化するとき，すべてのチーズを浄化するのに必要な最小のパターン数を答える．

パターンとは 0, 1, * からなる長さ N の列で，1つのパターンには高々1つしか * は含まれない． * の桁の数字は 0 にも 1 にもマッチする． 例えば N = 6 のとき，01*100 というパターンは，チーズ 010100 とチーズ 011100 にマッチする．

制約

解法

* を使って1つのパターンで浄化できるペア，すなわちハミング距離が1のペアにエッジを張って二部グラフの最大マッチングを求めれば，それが * を使ってまとめられるペアの最大の数であるため，チーズの個数からこれを引いたものが答えになる．

  1 #include <iostream>
  2 #include <vector>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 bool bm_augment(const vector<vector<int> >& g, int u, vector<int>& match_to, vector<bool>& visited)/*{{{*/
  7 {
  8   if (u < 0) {
  9     return true;
 10   }
 11 
 12   for (vector<int>::const_iterator it(g[u].begin()); it != g[u].end(); ++it) {
 13     if (!visited[*it]) {
 14       visited[*it] = true;
 15       if (bm_augment(g, match_to[*it], match_to, visited)) {
 16         match_to[*it] = u;
 17         return true;
 18       }
 19     }
 20   }
 21   return false;
 22 }/*}}}*/
 23 
 24 void coloring(const vector<vector<int> >& g, int u, vector<int>& color)/*{{{*/
 25 {
 26   for (vector<int>::const_iterator it = g[u].begin(); it != g[u].end(); ++it) {
 27     if (color[*it] == 0) {
 28       color[*it] = -color[u];
 29       coloring(g, *it, color);
 30     }
 31   }
 32 }/*}}}*/
 33 
 34 int bipartite_matching(const vector<vector<int> >& g)/*{{{*/
 35 {
 36   const int N = g.size();
 37   vector<int> color(N, 0);
 38   for (int u = 0; u < N; u++) {
 39     if (color[u] == 0) {
 40       color[u] = 1;
 41       coloring(g, u, color);
 42     }
 43   }
 44   vector<int> match_to(N, -1);
 45   int match = 0;
 46   vector<bool> visited(N);
 47   for (int u = 0; u < N; u++) {
 48     if (color[u] == 1) {
 49       fill(visited.begin(), visited.end(), false);
 50       if (bm_augment(g, u, match_to, visited)) {
 51         match++;
 52       }
 53     }
 54   }
 55   return match;
 56 }/*}}}*/
 57 
 58 int main()
 59 {
 60   int N, M;
 61   while (cin >> N >> M && N != 0) {
 62     vector<int> v;
 63     for (int i = 0; i < M; i++) {
 64       string s;
 65       cin >> s;
 66       if (s.find('*') != string::npos) {
 67         int n = 0, m = 0;
 68         for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
 69           if (*it == '*') {
 70             n = 2*n + 0;
 71             m = 2*m + 1;
 72           } else {
 73             n = 2*n + (*it-'0');
 74             m = 2*m + (*it-'0');
 75           }
 76         }
 77         v.push_back(n);
 78         v.push_back(m);
 79       } else {
 80         int n = 0;
 81         for (string::const_iterator it = s.begin(); it != s.end(); ++it) {
 82           n = 2*n + (*it-'0');
 83         }
 84         v.push_back(n);
 85       }
 86     }
 87     sort(v.begin(), v.end());
 88     v.erase(unique(v.begin(), v.end()), v.end());
 89 
 90     vector<vector<int> > g(1<<N);
 91     for (vector<int>::const_iterator it = v.begin(); it != v.end(); ++it) {
 92       for (vector<int>::const_iterator jt = it+1; jt != v.end(); ++jt) {
 93         if (__builtin_popcount(*it ^ *jt) == 1) {
 94           g[*it].push_back(*jt);
 95           g[*jt].push_back(*it);
 96         }
 97       }
 98     }
 99 
100     cout << v.size()-bipartite_matching(g) << endl;
101   }
102   return 0;
103 }
poj/2724.cc