Flood Fill

好习惯：先看样例，直接手模。

手摸完第一个样例我们会发现:

当两个值不一样的连通块相邻时，我们若翻转其中一个，再翻转另外一个的时候，与直接翻转另外一个没有区别。

举个例子：010

我们先翻转 1，变成了 000，此时我们再翻转 000 则变成了 111。

与直接翻转 010 两边的 0 变成 111 没有任何区别。

所以我们大胆猜测将一个连通块变为一个点。

所以知道我们在选择翻转一个连通块的时候不用翻转周围的连通块。

所以显然我们能只翻一个或者都不翻。

问题来了，我们该怎么处理这个？？？

请看下图：

其中 0 的点表示数值为 0 的连通块，1 的点同理。边上的 翻转 表示连通块翻转的话会造成的花费(也就是翻转后 A 图与 B 图不同的点的个数)， 不翻转 同理。

这样就能保证我们的最小割的容量不存在同时翻转的贡献了。

#include <bits/stdc++.h>

int N, M;
int S = 1, T = 2;
int tot = 2, id[1100][1100];
int A[1100][1100], B[1100][1100];
int cnt = 1, head[1100000], next[2100000], to[2100000], value[2100000];

void AddEdge(int u, int v, int val) {
    ++ cnt;
    next[cnt] = head[u];
    head[u] = cnt;
    to[cnt] = v;
    value[cnt] = val;
}

class DisjointSet {
public:
    int fat[1100000];
    int size[1100000];
    int different[1100000]    ;
    void clear() {
        for (int i = 1; i <= N * M + 100; ++ i) {
            fat[i] = i;
            size[i] = 1;
            different[i] = 0;
        }
    }
    int Find(int x) {
        if (fat[x] != x)
            fat[x] = Find(fat[x]);
        return fat[x];
    }
    void Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        if (x != y) {
            fat[x] = y;
            size[y] += size[x];
            different[y] += different[x];
        }
    }
    void Add(int x) {
        x = Find(x);
        different[x] ++;
    }
}set;

std::pair<int, int> origin[1100000];
std::set<std::pair<int, int>> Set;
bool visit[1100000];
int answer;

namespace Dinic {
    int deep[1100000], cur[1100000];
    void clear() {
        for (int i = 1; i <= tot; ++ i) {
            deep[i] = 0;
            cur[i] = head[i];
        }
    }
    bool Bfs(int begin, int end) {
        clear();
        deep[begin] = 1;
        std::queue<int> queue;
        queue.emplace(begin);
        while (queue.size()) {
            int now = queue.front();
            queue.pop();
            for (int i = head[now]; i; i = next[i]) {
                if (!value[i] || deep[to[i]])
                    continue;
                deep[to[i]] = deep[now] + 1;
                if (to[i] == end)
                    return true;
                queue.emplace(to[i]);
            }
        }
        return false;
    }
    int Dfs(int now, int end, int flow) {
        if (now == end)
            return flow;
        int rest = flow, temp;
        for (int i = cur[now]; i && rest; i = next[i]) {
            cur[now] = i;
            if (value[i] && deep[to[i]] == deep[now] + 1) {
                temp = Dfs(to[i], end, std::min(rest, value[i]));
                if (!temp)
                    deep[to[i]] = 0;
                value[i] -= temp;
                value[i ^ 1] += temp;
                rest -= temp;
            }
        }
        return flow - rest;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);

    std::cin >> N >> M;
    set.clear();
    memset(A, -1, sizeof(A));
    for (int i = 1; i <= N; ++ i) {
        for (int j = 1; j <= M; ++ j) {
            char ch;
            std::cin >> ch;
            A[i][j] = ch - '0';
            id[i][j] = ++ tot;
        }
    }
    for (int i = 1; i <= N; ++ i) {
        for (int j = 1; j <= M; ++ j) {
            char ch;
            std::cin >> ch;
            B[i][j] = ch - '0';
            if (A[i][j] != B[i][j]) 
                set.Add(id[i][j]);
            if (A[i][j] == A[i - 1][j]) 
                set.Union(id[i][j], id[i - 1][j]);
            if (A[i][j] == A[i][j - 1])
                set.Union(id[i][j], id[i][j - 1]);
        }
    }
    for (int i = 1; i <= N; ++ i) {
        for (int j = 1; j <= M; ++ j) {
            int now = set.Find(id[i][j]);
            int different = set.different[now];
            int same = set.size[now] - set.different[now];
            if (!visit[now]) {
                visit[now] = true;
                if (A[i][j] == 0) {
                    AddEdge(S, now, different);
                    AddEdge(now, S, 0);
                    AddEdge(now, T, same);
                    AddEdge(T, now, 0);
                }
                else {
                    AddEdge(S, now, same);
                    AddEdge(now, S, 0);
                    AddEdge(now, T, different);
                    AddEdge(T, now, 0);
                }
            }

            if (A[i][j] + A[i - 1][j] == 1) {
                int x = set.Find(id[i][j]);
                int y = set.Find(id[i - 1][j]);
                if (A[i][j] == 0)
                    Set.emplace(x, y);
                else
                    Set.emplace(y, x);
            }
            if (A[i][j] + A[i][j - 1] == 1) {
                int x = set.Find(id[i][j]);
                int y = set.Find(id[i][j - 1]);
                if (A[i][j] == 0)
                    Set.emplace(x, y);
                else
                    Set.emplace(y, x);
            }
        }
    }
    for (const std::pair<int, int> &iter: Set) {
        AddEdge(iter.first, iter.second, 1e9);
        AddEdge(iter.second, iter.first, 0);
    }
    while (Dinic::Bfs(S, T))
        answer += Dinic::Dfs(S, T, 1e9);
    std::cout << answer << '\n';
    return 0;
}