Submission #3265142

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

struct max_flow {
    struct edge { int to, cap, rev; };
    int V;
    vector<vector<edge>> G;
    vector<int> itr, level;

    max_flow(int V) : V(V) { G.assign(V,vector<edge>()); }

    void add_edge(int from, int to, int cap) {
        G[from].push_back((edge) {to, cap, (int) G[to].size()});
        G[to].push_back((edge) {from, 0, (int) G[from].size()-1});
    }

    void bfs(int s) {
        level.assign(V,-1);
        queue<int> q;
        level[s] = 0; q.push(s);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for(auto &e: G[v]){
                if (e.cap > 0 and level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.push(e.to);
                }
            }
        }
    }

    int dfs(int v, int t, int f) {
        if (v == t) return f;
        for (int& i = itr[v]; i < (int) G[v].size(); ++i) {
            edge& e = G[v][i];
            if (e.cap > 0 and level[v] < level[e.to]) {
                int d = dfs(e.to, t, min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    int run(int s, int t) {
        int ret = 0, f;
        while (bfs(s), level[t] >= 0) {
            itr.assign(V,0);
            while ((f = dfs(s, t, INF)) > 0) ret += f;
        }
        return ret;
    }
};

int main() {
    //cout.precision(10);
    max_flow graph(5050);
    int n, m;
    cin >> m >> n;
    int a[75][75];
    int b[75][75];
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            cin >> a[i][j];
        }
    }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            cin >> b[i][j];
        }
    }
    int ans = 0;
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(!((a[i][j] == 1) && (b[i][j] == 0))){
                continue;
            }
            ans++;
            graph.add_edge(i * 70 + j, 5040, 1);
        }
    }
    int di[4] = {1, -1, 0, 0};
    int dj[4] = {0, 0, 1, -1};
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(!((a[i][j] == 0) && (b[i][j] == 1))){
                continue;
            }
            ans++;
            graph.add_edge(0, i * 70 + j, 1);
            for(int k = 0; k <= 3; k++){
                int newi = i + di[k];
                int newj = j + dj[k];
                if(newi <= 0){
                    continue;
                }
                if(newj <= 0){
                    continue;
                }
                if(newi > m){
                    continue;
                }
                if(newj > n){
                    continue;
                }
                if((a[newi][newj] == 1) && (b[newi][newj] == 0)){
                    graph.add_edge(i * 70 + j, newi * 70 + newj, 1);
                }
            }
        }
    }
    cout << ans - graph.run(0, 5040) << endl;
    return 0;
}

Submission Info

Judge Result