題干：

一次舞會(huì)有n個(gè)男孩和n個(gè)女孩。每首曲子開始時(shí)，所有男孩和女孩恰好配成n對(duì)跳交誼舞。每個(gè)男孩都不會(huì)和同一個(gè)女孩跳兩首（或更多）舞曲。有一些男孩女孩相互喜歡，而其他相互不喜歡（不會(huì)“單向喜歡”）。每個(gè)男孩最多只愿意和k個(gè)不喜歡的女孩跳舞，而每個(gè)女孩也最多只愿意和k個(gè)不喜歡的男孩跳舞。給出每對(duì)男孩女孩是否相互喜歡的信息，舞會(huì)最多能有幾首舞曲？

Input

第一行包含兩個(gè)整數(shù)n和k。以下n行每行包含n個(gè)字符，其中第i行第j個(gè)字符為'Y'當(dāng)且僅當(dāng)男孩i和女孩j相互喜歡。

Output

僅一個(gè)數(shù)，即舞曲數(shù)目的最大值。

Sample Input

3 0

YYY

YYY

YYY

Sample Output

3

Hint

N<=50 K<=30

解題報(bào)告：

? 這題網(wǎng)絡(luò)流，做法很多。可以直接二分可以跳多少支舞，然后網(wǎng)絡(luò)流check一下。也可以每次每次的跑，直到第一次湊不滿n個(gè)人為止。也可以每次給他一條流量為1的空間，讓他湊n個(gè)人，然后再給他流量為1的空間，讓他在殘留網(wǎng)絡(luò)上湊n個(gè)人，這樣直到第一次湊不出n個(gè)人的時(shí)候break。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; int n,k,N; int tot; struct Edge {int to,ne,w; } e[100005 * 2]; int head[10005]; int st,ed; int dis[10050],q[10005]; void add(int u,int v,int w,int rw=0) {e[++tot].to=v;e[tot].w=w;e[tot].ne=head[u];head[u]=tot;e[++tot].to=u;e[tot].w=rw;e[tot].ne=head[v];head[v]=tot; } bool bfs(int st,int ed) {memset(dis,-1,sizeof(dis));int front=0,tail=0;q[tail++]=st;dis[st]=0;while(front<tail) {int cur = q[front];if(cur == ed) return 1;front++;for(int i = head[cur]; i!=-1; i = e[i].ne) {if(e[i].w&&dis[e[i].to]<0) {q[tail++]=e[i].to;dis[e[i].to]=dis[cur]+1;}}}if(dis[ed]==-1) return 0;return 1; } int dfs(int cur,int limit) {//limit為源點(diǎn)到這個(gè)點(diǎn)的路徑上的最小邊權(quán) if(limit==0||cur==ed) return limit;int w,flow=0;for(int i = head[cur]; i!=-1; i = e[i].ne) { if(e[i].w&&dis[e[i].to]==dis[cur]+1) {w=dfs(e[i].to,min(limit,e[i].w));e[i].w-=w;e[i^1].w+=w;flow+=w;limit-=w;if(limit==0) break;}}if(!flow) dis[cur]=-1;return flow; } int dinic() {int ans = 0;while(bfs(st,ed)) ans+=dfs(st,0x7fffffff);return ans; } char s[55][55]; int main() {cin>>n>>k;st=4*n+1,ed=st+1;N=ed+1;//init tot=1;for(int i = 1; i<=N; i++) head[i] = -1;for(int i = 1; i<=n; i++) {scanf("%s",s[i]+1);add(i,i+n,k);add(i+2*n,i+3*n,k); }for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {if(s[i][j] == 'Y') add(i,j+3*n,1);else add(i+n,j+2*n,1);}}for(int ans = 0; ;ans++) {for(int i = 1; i<=n; i++) {add(st,i,1);add(3*n+i,ed,1);}if(dinic() != n) {printf("%d\n",ans);break;} } return 0; }

總結(jié)

以上是生活随笔為你收集整理的【BZOJ - 1305】dance跳舞（拆点网络流，建图，最大流，残留网络上跑最大流）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。