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

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

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 5550;
const int MAXM = 1000005;
const int INF = 1000000050;
int Head[MAXN], cur[MAXN], lev[MAXN], to[MAXM << 1], nxt[MAXM << 1], f[MAXM << 1], ed = 1, 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] = 0;return;
}
inline bool BFS()
{int u;memset(lev, -1, sizeof(lev));queue<int>q;lev[S] = 0;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]] == -1) {lev[to[i]] = lev[u] + 1;q.push(to[i]);/*if (to[i] == T){return 1;}magic one way optimize*/}}memcpy(cur, Head, sizeof Head);return lev[T] != -1;
}
inline int DFS(int u, int maxf)
{if (u == T || !maxf) {return maxf;}int cnt = 0;for (int &i = cur[u], tem; i; i = nxt[i])if (f[i] && lev[to[i]] == lev[u] + 1) {tem = DFS(to[i], min(maxf, f[i]));maxf -= tem;f[i] -= tem;f[i ^ 1] += tem;cnt += tem;if (!maxf) {break;}}if (!cnt) {lev[u] = -1;}return cnt;
}
int Dinic()
{int ans = 0;while (BFS()) {ans += DFS(S, 2147483647);}return ans;
}
void init(int SS, int TT)
{memset(Head, 0, sizeof(Head));ed = 1;S = SS;T = TT;return;
}
char ff[205][205];
int dir[5][2];
int aim[205][205];
int cnt = 0;
int main()
{int n, m;int r, c;int u, v;scanf("%d %d %d %d", &n, &m, &r, &c);dir[1][0] = dir[2][1] = r;dir[1][1] = dir[2][0] = c;dir[3][0] = c, dir[4][0] = r;dir[3][1] = -r, dir[4][1] = -c;if(r==c){dir[2][0]=dir[2][1]=dir[4][0]=dir[4][1]=50;}for (int i = 1; i <= n; i++) {scanf("%s", ff[i]+1);}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (ff[i][j] == '.') {aim[i][j] = ++cnt;}}}S = 0, T = 2 * cnt + 1;for (int i = 1; i <= cnt; i++) {addedge(S, i, 1);addedge(cnt + i, T, 1);}for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++) {if (ff[i][j] == '.') {for (int k = 1; k <= 4; k++) {int dx = i + dir[k][0];int dy = j + dir[k][1];if (dx >= 1 && dx <= n && dy >= 1 && dy <= m) {if (ff[dx][dy] == '.') {u = aim[i][j], v = aim[dx][dy] + cnt;addedge(u, v, 1);//cout<<i<<" "<<j<<" "<<dx<<" "<<dy<<endl;
                        }}}}}cout << cnt - Dinic() << endl;return 0;
}