這是一道最大流的模版題

一定要記住不能開出來重點呀

#include <queue> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int MAXN=205; const int MAXM=6005; const int inf=0x3f3f3f3f; inline int read(){int x=0,f=1,ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f; } inline int cread(){int ch=getchar();while(ch<'A'||ch>'Z') ch=getchar();return ch; } int nxt[MAXM],to[MAXM],cap[MAXM],h[MAXN],cnt; inline void add(int x,int y,int k){nxt[cnt]=h[x];to[cnt]=y;cap[cnt]=k;h[x]=cnt++;nxt[cnt]=h[y];to[cnt]=x;cap[cnt]=0;h[y]=cnt++; } int dep[MAXN]; queue<int> q; inline bool bfs(int s,int t){// cout<<s<<"\t"<<t<<endl;while(!q.empty()) q.pop();memset(dep,0,sizeof(dep));dep[s]=1;q.push(s);while(!q.empty()){int e=q.front();q.pop();for(int i=h[e];i!=-1;i=nxt[i])if(cap[i]&&dep[to[i]]==0)dep[to[i]]=dep[e]+1,q.push(to[i]);}return dep[t]?1:0; } int T; inline int dfs(int x,int k){if(x==T) return k;int res=0;for(int i=h[x];i!=-1&&k;i=nxt[i])if(cap[i]&&dep[to[i]]==dep[x]+1){int d=dfs(to[i],min(k,cap[i]));if(d) cap[i]-=d,cap[i^1]+=d,res+=d,k-=d;}if(!res) dep[x]=0;return res; } int n,k; inline int dinic(){int res=0;T=(n+1)<<2;while(bfs(0,T)) res+=dfs(0,inf);return res; } int map[55][55]; inline bool ok(int x){memset(h,-1,sizeof(h));cnt=0;for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){if(map[i][j]) add(i<<1,(j+n)<<1,1);else add(i<<1|1,(j+n)<<1|1,1);}for(int i=1;i<=n;++i) add(0,i<<1,x),add((i+n)<<1,(n+1)<<2,x);for(int i=1;i<=n;++i) add(i<<1,i<<1|1,k),add((i+n)<<1|1,(i+n)<<1,k);return (dinic()>=x*n); } int main(){n=read(),k=read();for(int i=1;i<=n;++i)for(int j=1;j<=n;++j){int c=cread();if(c=='Y') map[i][j]=1;}int l=0,r=n;while(l<r){// cout<<l<<"\t"<<r<<endl;int mid=(l+r)>>1;if(ok(mid+1)) l=mid+1;else r=mid;}printf("%d\n",l);return 0; }

　　

轉載于:https://www.cnblogs.com/gcyyzf/p/10058433.html

總結

以上是生活随笔為你收集整理的BZOJ 1305 [CQOI2009]dance跳舞的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。