BZOJ_1305.cpp

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int MAXN=300+10;
const int inf=1e9;

struct Edge {
	int v, cap;
	Edge *next, *op;
	Edge(){}
	Edge(int _v, int _c, Edge* _n):v(_v), cap(_c), next(_n){}
};

Edge *E[MAXN];
int Q[MAXN];
int level[MAXN];
int N, K, cnt;
int S, T;

void addedge(int u, int v, int a, int b) {
	E[u]=new Edge(v, a, E[u]); E[v]=new Edge(u, b, E[v]);
	E[u]->op=E[v]; E[v]->op=E[u];
}

bool dinic_bfs() {
	memset(level, -1, sizeof(level));
	level[S]=0; Q[0]=S;
	for (int h=0, t=1; h<t; h++) {
		int u=Q[h], v;
		for (Edge *p=E[u]; p; p=p->next)
			if (level[v=p->v]==-1&&p->cap>0) {
				level[v]=level[u]+1;
				Q[t++]=v;
			}
	}
	return (level[T]!=-1);
}

int dinic_dfs(int u, int low) {
	if (u==T) return low;
	int ret=0, tmp, v;
	for (Edge *p=E[u]; p&&ret<low; p=p->next) 
		if (level[v=p->v]==level[u]+1&&p->cap>0) {
			if (tmp=dinic_dfs(v, min(low-ret, p->cap))) {
				ret+=tmp; p->cap-=tmp; p->op->cap+=tmp;
			}
		}
	if (!ret) level[u]=-1; return ret;
}

int dinic() {
	int maxflow=0, t;
	while (dinic_bfs()) {
		while (t=dinic_dfs(S, inf)) maxflow+=t;
	}
	return maxflow;
}

int main() {
	scanf("%d%d", &N, &K);
	memset(E, 0, sizeof(E));
	S=0; T=6*N+1;
	for (int i=1; i<=N; i++) {
		char buf[100]; scanf("%s", buf+1);
		addedge(S, i, 0, 0); addedge(5*N+i, T, 0, 0);
		addedge(i, N+i, K, 0); addedge(4*N+i, 5*N+i, K, 0);
		addedge(i, 2*N+i, inf, 0); addedge(3*N+i, 5*N+i, inf, 0);
		for (int j=1; j<=N; j++) {
			if (buf[j]=='Y') {
				addedge(2*N+i, 3*N+j, 1, 0);
			}
			else {
				addedge(N+i, 4*N+j, 1, 0);
			}
		}
	}
	int flow=0;
	for (int i=1;;i++) {
		for (Edge *p=E[S]; p; p=p->next) p->cap++;
		for (Edge *p=E[T]; p; p=p->next) p->op->cap++;
		flow+=dinic();
		if (flow!=i*N) {
			printf("%d\n", i-1);
			break;
		}
	}
	return 0;
}