P2172 [国家集训队]部落战争 二分图最小不相交路径覆盖

二分图最小不相交路径覆盖

#include<bits/stdc++.h>

using namespace std;

const int MAXN = ;

const int MAXM = ;

const int INF = ;

int Head[MAXN], cur[MAXN], lev[MAXN], to[MAXM << ], nxt[MAXM << ], f[MAXM << ], ed = , S, T;

inline void addedge(int u, int v, int cap)

{

    to[++ed] = v;

    nxt[ed] = Head[u];

    Head[u] = ed;

    f[ed] = cap;

    to[++ed] = u;

    nxt[ed] = Head[v];

    Head[v] = ed;

    f[ed] = ;

    return;

}

inline bool BFS()

{

    int u;

    memset(lev, -, sizeof(lev));

    queue<int>q;

    lev[S] = ;

    q.push(S);

    while (q.size()) {

        u = q.front();

        q.pop();

        for (int i = Head[u]; i; i = nxt[i])

            if (f[i] && lev[to[i]] == -) {

                lev[to[i]] = lev[u] + ;

                q.push(to[i]);

                /*

                if (to[i] == T)

                {

                        return 1;

                }

                magic one way optimize

                */

            }

    }

    memcpy(cur, Head, sizeof Head);

    return lev[T] != -;

}

inline int DFS(int u, int maxf)

{

    if (u == T || !maxf) {

        return maxf;

    }

    int cnt = ;

    for (int &i = cur[u], tem; i; i = nxt[i])

        if (f[i] && lev[to[i]] == lev[u] + ) {

            tem = DFS(to[i], min(maxf, f[i]));

            maxf -= tem;

            f[i] -= tem;

            f[i ^ ] += tem;

            cnt += tem;

            if (!maxf) {

                break;

            }

        }

    if (!cnt) {

        lev[u] = -;

    }

    return cnt;

}

int Dinic()

{

    int ans = ;

    while (BFS()) {

        ans += DFS(S, );

    }

    return ans;

}

void init(int SS, int TT)

{

    memset(Head, , sizeof(Head));

    ed = ;

    S = SS;

    T = TT;

    return;

}

char ff[][];

int dir[][];

int aim[][];

int cnt = ;

int main()

{

    int n, m;

    int r, c;

    int u, v;

    scanf("%d %d %d %d", &n, &m, &r, &c);

    dir[][] = dir[][] = r;

    dir[][] = dir[][] = c;

    dir[][] = c, dir[][] = r;

    dir[][] = -r, dir[][] = -c;

    if(r==c)

    {

        dir[][]=dir[][]=dir[][]=dir[][]=;

    }

    for (int i = ; i <= n; i++) {

        scanf("%s", ff[i]+);

    }

    for (int i = ; i <= n; i++) {

        for (int j = ; j <= m; j++) {

            if (ff[i][j] == '.') {

                aim[i][j] = ++cnt;

            }

        }

    }

    S = , T =  * cnt + ;

    for (int i = ; i <= cnt; i++) {

        addedge(S, i, );

        addedge(cnt + i, T, );

    }

    for (int i = ; i <= n; i++)

        for (int j = ; j <= m; j++) {

            if (ff[i][j] == '.') {

                for (int k = ; k <= ; k++) {

                    int dx = i + dir[k][];

                    int dy = j + dir[k][];

                    if (dx >=  && dx <= n && dy >=  && dy <= m) {

                        if (ff[dx][dy] == '.') {

                            u = aim[i][j], v = aim[dx][dy] + cnt;

                            addedge(u, v, );

                            //cout<<i<<" "<<j<<" "<<dx<<" "<<dy<<endl;

                        }

                    }

                }

            }

        }

    cout << cnt - Dinic() << endl;

    return ;

}