TCO2012 2A

参加記録。何も出来なかった。

300 :
2部マッチングして正当性を確かめるまでは思い浮かんだけど
log2 で分類しきれるという所に最後まで気がつかなかった。
もっとシンプルな方法で解いてる人がいるけど、あれは何をやっているのか・・・。

450 :
読んだだけ。

1000 :
開いてない。



300

const int V = 50 * 2 + 2 + 10;

struct E {
  int src, dst;
  E(int s, int d) : src(s), dst(d) {}
};
vector<E> g[V];

bool vis[V];
int path[V];

int cap[V][V];

bool rec(int node, int snk, int size)
{
  if (node == snk) return true;
  vis[node] = true;
  each (e, g[node]) {
    if (cap[e->src][e->dst] <= 0 || vis[e->dst]) continue;
    path[e->dst] = e->src;
    if (rec(e->dst, snk, size)) return true;
  }
  return false;
}

int flow(int src, int snk, int size)
{
  int res = 0;
  fill(vis, vis + size, false);
  while (rec(src, snk, size)) {
    fill(vis, vis + size, false);
    for (int i = snk; i != src; i = path[i]) {
      --cap[path[i]][i];
      ++cap[i][path[i]];
    }
    ++res;
  }
  return res;
}

class SwitchesAndLamps {
public:
  int theMin(vector <string> S, vector <string> L)
  {
    const int size = S[0].size();   
    const int src = size * 2;
    const int snk = size * 2 + 1;

    fill(g, g + V, vector<E>());
    fill(&cap[0][0], &cap[V - 1][V], 0);

    for (int s = 0; s < (int)size; ++s) {
      for (int l = 0; l < (int)size; ++l) {
        bool flg = true;
        for (int i = 0; i < (int)S.size(); ++i) {
          flg = flg && S[i][s] == L[i][l];
        }
        if (flg) {
          g[s].push_back(E(s, l + size));
          g[l + size].push_back(E(l + size, s));
          cap[s][l + size] = 1;
        }
      }
    }

    for (int s = 0; s < (int)size; ++s) {
      cap[src][s] = 1;
      g[src].push_back(E(src, s));     
    }

    for (int l = 0; l < (int)size; ++l) {
      cap[l + size][snk] = 1;
      g[l + size].push_back(E(l + size, snk));
    }

    if (size != flow(src, snk, snk + 1)) return -1;

    int mx = 0;
    for (int i = 0; i < size; ++i) {
      mx = max(mx, (int)g[i].size());
    }   
    return (int)ceil(log2(mx));
  }
};