http://hzwer.com/1986.html
#include#include #include #include using namespace std;#define INF 2147483647#define N 51int n,m;char a[N][N];queue q;int S,T,nn;int first[(N<<2)+3],next[2*N*(N+5)],v[2*N*(N+5)],cap[2*N*(N+5)],en;int d[(N<<2)+3],cur[(N<<2)+3];void AddEdge(int U,int V,int Cap){ v[en]=V; cap[en]=Cap; next[en]=first[U]; first[U]=en++; v[en]=U; cap[en]=0; next[en]=first[V]; first[V]=en++;}bool bfs(){ memset(d,-1,sizeof(int)*(nn+1)); q.push(S); d[S]=0; while(!q.empty()) { int U=q.front(); q.pop(); for(int i=first[U];i!=-1;i=next[i]) if(d[v[i]]==-1&&cap[i]) { d[v[i]]=d[U]+1; q.push(v[i]); } } return d[T]!=-1;}int dfs(int U,int a){ if(U==T||(!a)) return a; int Flow=0,f; for(int i=first[U];i!=-1;i=next[i]) if(d[v[i]]==d[U]+1&&(f=dfs(v[i],min(a,cap[i])))) { cap[i]-=f; cap[i^1]+=f; Flow+=f; a-=f; if(!a) break; } if(!Flow) d[U]=-1; return Flow;}int MaxFlow(){ int Flow=0,tmp; while(bfs()) { memcpy(cur,first,sizeof(int)*(nn+1)); while(tmp=dfs(S,INF)) Flow+=tmp; } return Flow;}bool check(int Lim){ memset(first,-1,sizeof(int)*(nn+1)); en=0; for(int i=1;i<=n;++i) { AddEdge(S,1+i,Lim); AddEdge(1+(n<<1)+i,T,Lim); AddEdge(1+i,1+n+i,m); AddEdge(1+n*3+i,1+(n<<1)+i,m); } for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(a[i][j]=='Y') AddEdge(1+i,1+(n<<1)+j,1); else AddEdge(1+n+i,1+n*3+j,1); return MaxFlow()==n*Lim;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;++i) scanf("%s",a[i]+1); int l=0,r=50; S=1; T=(n<<2)+2; nn=(n<<2)+2; while(r>l) { int mid=(l+r+1>>1); if(check(mid)) l=mid; else r=mid-1; } printf("%d\n",l); return 0;}