【CQOI2009】bzoj1305 跳舞

2023-11-07 20:39

文章标签 跳舞 cqoi2009 bzoj1305

本文主要是介绍【CQOI2009】bzoj1305 跳舞，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

Input

第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为’Y’当且仅当男孩i和女孩j相互喜欢。

Output

仅一个数，即舞曲数目的最大值。

二分舞曲个数x，然后验证。
把每个人分成三个点，表示整体、喜欢的和不喜欢的。从原点向男孩整体连容量为x的边，从整体向喜欢连正无穷的边，向不喜欢连k的边。女孩也做同样处理。然后男女生互相喜欢的从喜欢节点向喜欢节点连1的边，互相不喜欢的从不喜欢节点到不喜欢节点连1的边，最后验证流量是否为x。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int oo=0x3f3f3f3f;
int fir[500],ne[10000],to[10000],w[10000],f[500],que[500],n,k,tot,s,t;
bool b[60][60];
/*boy: all:i like:i+n dis:i+2*n
girl: all:i+3*n like:i+4*n dis:i+5*n*/
void add(int num,int u,int v,int l)
{ne[num]=fir[u];fir[u]=num;to[num]=v;w[num]=l;
}
void init()
{int i,j;char ss[100];scanf("%d%d",&n,&k);s=6*n+1;t=6*n+2;for (i=1;i<=n;i++){scanf("%s",ss+1);for (j=1;j<=n;j++)b[i][j]=ss[j]=='Y';}
}
void build(int x)
{int i,j;for (i=1;i<=n;i++){add(tot++,s,i,x);add(tot++,i,s,0);add(tot++,i,i+n,oo);add(tot++,i+n,i,0);add(tot++,i,i+n*2,k);add(tot++,i+n*2,i,0);add(tot++,i+3*n,t,x);add(tot++,t,i+3*n,0);add(tot++,i+n*4,i+n*3,oo);add(tot++,i+n*3,i+n*4,0);add(tot++,i+n*5,i+n*3,k);add(tot++,i+n*3,i+n*5,0);}for (i=1;i<=n;i++)for (j=1;j<=n;j++)if (b[i][j]){add(tot++,i+n,j+n*4,1);add(tot++,j+n*4,i+n,0);}else{add(tot++,i+n*2,j+n*5,1);add(tot++,j+n*5,i+n*2,0);}
}
bool find()
{int hd=1,tl=1,u,v,i;que[1]=s;memset(f,0,sizeof(f));f[s]=1;while (hd<=tl){u=que[hd++];for (i=fir[u];i;i=ne[i])if (w[i]&&!f[v=to[i]]){f[v]=f[u]+1;que[++tl]=v;}}return f[t];
}
int dfs(int u,int lim)
{if (u==t) return lim;int x,v,i,ret=0;for (i=fir[u];i;i=ne[i])if (w[i]&&f[v=to[i]]==f[u]+1){x=dfs(v,min(lim-ret,w[i]));w[i]-=x;w[i^1]+=x;ret+=x;}if (!ret) f[u]=0;return ret;
}
bool ok(int x)
{int i,j,ans=0,temp;memset(fir,0,sizeof(fir));memset(ne,0,sizeof(ne));tot=2;build(x);while (find())while (temp=dfs(s,oo))ans+=temp;return ans==x*n;
}
int main()
{init();int l=0,r=n,mid;while (l<r){mid=(l+r+1)/2;if (ok(mid)) l=mid;else r=mid-1;}printf("%d\n",l);
}