450 P8XMatrixRecovery

2011-12-20

19:06 |

解説とかいろいろ見てからコードだけ書いた。(practice system test pass)

２部マッチング問題の実装練習ということで。

maximumFlow() は spaghetti sourceさんより拝借。

すべての「?」について、まず０として列と列のマッチングに成功したら次へ、失敗したら１にして次へ。

最後に残ったものが辞書順最小かつヒントに矛盾しない答え。

こういう、いくつかのアルゴリズムを組み合わせる系ってすげぇと思う。

なんとかの最大値を求めるために解を仮定して二分探索するやつとか。

#define INF 1000000
typedef int Weight;
struct Edge {
 int src, dst;
 Weight weight;
 Edge(int src, int dst, Weight weight) :
   src(src), dst(dst), weight(weight) { }
};
bool operator < (const Edge &e, const Edge &f) {
 return e.weight != f.weight ? e.weight > f.weight : // !!INVERSE!!
   e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

typedef vector<Weight> Array;
typedef vector<Array> Matrix;

#define RESIDUE(s,t) (capacity[s][t]-flow[s][t])
Weight maximumFlow(const Graph &g, int s, int t) {
 int n = g.size();
 Matrix flow(n, Array(n)), capacity(n, Array(n));
 REP(u,n) FOR(e,g[u]) capacity[e->src][e->dst] += e->weight;

 Weight total = 0;
 while (1) {
   queue<int> Q; Q.push(s);
   vector<int> prev(n, -1); prev[s] = s;
   while (!Q.empty() && prev[t] < 0) {
     int u = Q.front(); Q.pop();
     FOR(e,g[u]) if (prev[e->dst] < 0 && RESIDUE(u, e->dst) > 0) {
       prev[e->dst] = u;
       Q.push(e->dst);
     }
   }
   if (prev[t] < 0) return total; // prev[x] == -1 <=> t-side
   Weight inc = INF;
   for (int j = t; prev[j] != j; j = prev[j])
     inc = min(inc, RESIDUE(prev[j], j));
   for (int j = t; prev[j] != j; j = prev[j])
     flow[prev[j]][j] += inc, flow[j][prev[j]] -= inc;
   VI path;
   for (int j = t; prev[j] != j; j = prev[j]) path.push_back(j);
   path.push_back(s);
   reverse(ALL(path));
   total += inc;
   //cout<<"Update "<<path<<" -> total "<<total<<endl;
 }
}
void add_edge(Graph& g, int s, int e, int w) {
   g[s].push_back(Edge(s, e, w));
   g[e].push_back(Edge(e, s, 0));
}
class P8XMatrixRecovery {
   public:
   vector <string> solve(vector <string> rows, vector <string> col) {
       int R = rows.size();
       int C = rows[0].size();
       REP(yy, R) {
           REP(xx, C) {
               if(rows[yy][xx]!='?') continue;
               rows[yy][xx] = '0';
               int t = C*2+2-1;
               //cout<<"BEGIN "<<xx<<" "<<yy<<endl;
               Graph g(C*2+2, Edges());
               REP(x, C) add_edge(g, 0, 1+x, 1);
               REP(x, C) add_edge(g, 1+C+x, t, 1);
               REP(x, C)
               REP(x1, C) {
                   int ee = 1;
                   REP(y, R) {
                       if(rows[y][x]=='?' || col[x1][y]=='?' || rows[y][x]==col[x1][y]) {
                       } else ee=0;
                   }
                   if(ee) add_edge(g, 1+x, 1+C+x1, 1);
               }
               if(C!=maximumFlow(g, 0, t)) {
                   rows[yy][xx] = '1';
               }
               //cout<<"RESULT "<<rows[yy][xx]<<endl;
           }
       }
       return rows;
   }