SRM 637 Div2 ConnectingGameDiv2 （復習）

練習で解きました．
http://apps.topcoder.com/wiki/display/tc/SRM+637

点連結度を用いて解きましたが，Editorialでは最小カットについて一言でしか述べていなかったので備忘録として残しておきます．

[Hard: ConnectingGameDiv2 ]

解法

次の3x3グリッドの具体例で考えます．
Aの連結成分の要素数は3,Bは1，Cは3，Dは2となっています．

次にグラフを作成していきます．
それぞれの連結成分を頂点として，連結成分の要素数を頂点の重みとします．
グリッド上で上下左右に隣接している連結成分同士を双方向に弧を張ります．
次に，頂点sとtを追加します．
頂点sからグリッド上で下の行（2行目）にある連結成分の頂点へ弧を張ります．
頂点tへグリッド上で上の行（0行目）にある連結成分の頂点から弧を張ります．
グラフを作成した結果が次の通りです．

元の問題で求めることをこのグラフ上で考えると，いくつかの頂点を除去してsからtへのパスが存在しないようにすることです．この時，除去した頂点の重み和を最小にするような頂点部分集合を求める問題となります．
上の問題では，{A,B}または{B,C}が答えとなり重み和は4となります．

この問題は重み和最小の分離集合を求める問題となります．
詳しい事は次を参考にしてください．
http://dopal.cs.uec.ac.jp/okamotoy/lect/2014/gn/handout10.pdf

上の資料を参考にグラフを変形して，sからtへの最大流を求めると答になります．
ただし，ある頂点を変形した頂点の弧の容量を頂点の重みとし，それ以外の弧の容量を無限大としています．変形したグラフはつぎのようになります．

ソースコード

実装が楽？になるように1x1グリッドの場合だけを特別扱いしています．
それ以外は，上の解法通りにグラフを変形して最大流（Dinic）問題に帰着しています．

/***************** Dinic Algorithm **************************/
typedef int Weight;
const Weight INF = 1e8;

struct Edge {
    int src, dst;
    Weight weight;
    int rev;
    Edge(int f, int t, Weight c, int rev = 0) :
        src(f), dst(t), weight(c), rev(rev) {}
};

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void AddEdge(Graph &g, int s, int dst, Weight cap){
    g[s].push_back(Edge(s, dst, cap, g[dst].size()));
    g[dst].push_back(Edge(dst, s, 0, g[s].size()-1));
}

void Bfs(const Graph &g, vector<int> &level, int s){
    level[s]=0;
    queue<int> que;
    que.push(s);
    while(!que.empty()){
        int v = que.front();
        que.pop();
        for (auto &e : g[v]) {
            if(e.weight > 0 && level[e.dst] < 0){
                level[e.dst] = level[v] + 1;
                que.push(e.dst);
            }
        }
    }
}

Weight Dfs(Graph &g, vector<int> &level, vector<int> &iter,
           int v, int t, Weight flow) {
    if(v == t)
        return flow;
    for (int &i = iter[v], N = g[v].size(); i < N; ++i) {
        Edge &e = g[v][i];

        if(e.weight > 0 && level[v] < level[e.dst]){
            Weight d = Dfs(g, level, iter, e.dst, t, min(flow, e.weight));
            if(d > 0){
                e.weight -= d;
                g[e.dst][e.rev].weight += d;
                return d;
            }
        }
    }
    return 0;
}

Weight Dinic(Graph &g, int s, int t){
    Weight flow = 0;

    while(true){
        vector<int> level(g.size(), -1);
        vector<int> iter(g.size(), 0);
        Bfs(g, level, s);

        if(level[t] < 0)
            break; // もう流せない
        Weight f = 0;
        while((f = Dfs(g, level, iter, s, t, INF)) > 0)
            flow += f;
    }

    return flow;
}
/***********************************************************/

const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};

class ConnectingGameDiv2 {
public:
    int getmin(vector <string> board) {
        const int H = board.size();
        const int W = board[0].size();
        
        // 1x1の場合
        if (H == 1 && W == 1)
            return 1;

        // 各々の連結成分に含まれる頂点数を数える
        map<char, int> cnt;
        for (int i = 0; i < H; ++i)
            for (int j = 0; j < W; ++j)
                ++cnt[board[i][j]];

        // ある連結成分に隣接している連結成分を調べる
        map<char, set<char>> connect;
        for (int i = 0; i < H; ++i) {
            for (int j = 0; j < W; ++j) {
                for (int d = 0; d < 4; ++d) {
                    int nx = j + dx[d];
                    int ny = i + dy[d];
                    if (nx < 0 || ny < 0 || nx >= W || ny >= H)
                        continue;
                    connect[board[i][j]].insert(board[ny][nx]);
                }
            }
        }

        // 各々の連結成分を自然数に対応させる
        map<char, int> change;
        int idx = 0;
        for (auto v : connect)
            change[v.first] = idx++;

        // 上の列に連結している連結成分t_vertexを調べる
        // 下の列に連結している連結成分s_vertexを調べる
        set<char> t_vertex, s_vertex;
        for (int i = 0; i < W; ++i) {
            t_vertex.insert(board[0][i]);
            s_vertex.insert(board[H - 1][i]);
        }

        // グラフの作成
        int V = 2 * cnt.size() + 2; // 頂点数
        Graph g(V);
        int s = V - 2, t = V - 1;
        int N = change.size();

        // 連結成分同士の弧を張る
        for (auto it : connect) {
            // 連結成分の入頂点をin,出頂点をoutとする
            int in = change[it.first], out = in + N;

            AddEdge(g, in, out, cnt[it.first]);

            for (auto it2 : it.second) {
                int v = change[it2];
                AddEdge(g, out, v, INF);
            }
        }

        // tとの弧を張る
        for (auto it : t_vertex) {
            int v = change[it] + N;
            AddEdge(g, v, t, INF);
        }
        // sとの弧を張る
        for (auto it : s_vertex) {
            int v = change[it];
            AddEdge(g, s, v, INF);
        }

        // 最大流を求める
        return Dinic(g, s, t);
    }
};