- #include < cstdio > #include < cstring > #include < iostream > #include < algorithm > using namespace std;#define maxn 505#define maxm 30005#define INF 0x3f3f3f3f int head[maxn],
- E[maxm],
- V[maxm],
- F[maxm],
- cnt;
- int n,
- k,
- deep[maxn],
- que[maxm << 1],
- s,
- t;
- char map[maxn][maxn];
- inline void edge_add(int u, int v, int f) {
- E[++cnt] = head[u],
- V[cnt] = v,
- F[cnt] = f,
- head[u] = cnt;
- E[++cnt] = head[v],
- V[cnt] = u,
- F[cnt] = 0,
- head[v] = cnt;
- }
- bool bfs() {
- for (int i = s; i <= t; i++) deep[i] = -1;
- que[0] = s,
- deep[s] = 0;
- int h = 0,
- tail = 1,
- now;
- while (h < tail) {
- now = que[h++];
- for (int i = head[now]; i; i = E[i]) {
- if (F[i] && deep[V[i]] < 0) {
- deep[V[i]] = deep[now] + 1;
- if (V[i] == t) return true;
- que[tail++] = V[i];
- }
- }
- }
- return false;
- }
- int flowing(int now, int flow) {
- if (now == t || flow <= 0) return flow;
- int oldflow = 0,
- pos;
- for (int i = head[now]; i; i = E[i]) {
- if (!F[i] || deep[V[i]] != deep[now] + 1) continue;
- pos = flowing(V[i], min(flow, F[i]));
- F[i] -= pos,
- F[i ^ 1] += pos,
- flow -= pos,
- oldflow += pos;
- if (!flow) return oldflow;
- }
- if (!oldflow) deep[now] = -1;
- return oldflow;
- }
- bool check(int mid) {
- cnt = 1;
- for (int i = s; i <= t; i++) head[i] = 0;
- for (int i = 1; i <= n; i++) edge_add(s, i, mid),
- edge_add(i, i + n, k);
- for (int i = n * 3 + 1; i <= n * 4; i++) edge_add(i, t, mid),
- edge_add(i - n, i, k);
- for (int i = 1; i <= n; i++) for (int v = 1; v <= n; v++) if (map[i][v] == 'Y') edge_add(i, v + n * 3, 1);
- else edge_add(i + n, n * 2 + v, 1);
- int res = 0;
- while (bfs()) res += flowing(s, INF);
- return res == mid * n;
- }
- int main() {
- scanf("%d%d", &n, &k),
- t = n * 4 + 1;
- for (int i = 1; i <= n; i++) scanf("%s", map[i] + 1);
- int l = 0,
- r = n,
- mid,
- ans = 0;
- while (l <= r) {
- mid = l + r >> 1;
- if (check(mid)) l = mid + 1,
- ans = mid;
- else r = mid - 1;
- }
- cout << ans;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2222977.html