bzoj-1305 dance舞蹈

bzoj-1305 dance跳舞

题意：

有n个男生和女生，男女之间要么互相喜欢要么互相不喜欢；

现在两两配对跳舞，两个人不能跳两次舞；

和不喜欢的人最多跳k次舞，求这些人可以跳多少轮舞；

n<=50，k<=30；

题解：

考虑网络流建图：

显然男生女生是不相交的，那么这就是个在二分图中的匹配问题；

每两个人之间都有跳舞的可能，但是有k这个数的限制；

所以就是每个男生和喜欢的女生有流量为1的边，和不喜欢的女生总计有流量为k 的边；

拆点建图之后枚举答案，每次从源点向男生，女生向汇点连流量为1的边；

跑最大流之后结果为n就是可以继续，当流量不为n时的的ans-1就是答案；

代码：

#include<queue>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 300
using namespace std;
queue<int>q;
int map[N][N],dis[N],n,tot;
char str[N];
void init()
{
	for(int i=1;i<=n;i++)
	map[0][i<<1]+=1;
	for(int i=1;i<=n;i++)
	map[(i+n)<<1][1]+=1;
}
bool bfs()
{
	memset(dis,-1,sizeof(dis));
	dis[0]=0;
	q.push(0);
	int x,i;
	while(!q.empty())
	{
		x=q.front(),q.pop();
		for(i=0;i<=tot;i++)
			if(dis[i]<0&&map[x][i]>0)
				q.push(i),dis[i]=dis[x]+1;
	}
	if(dis[1]<0)	return 0;
	else			return 1;
}
int dfs(int x,int k)
{
	if(x==1)	return k;
	int i,j,ret=0;
	for(i=0;i<=tot;i++)
	{
		if(map[x][i]>0&&dis[i]==dis[x]+1)
		{
			j=dfs(i,min(k-ret,map[x][i]));
			ret+=j;
			map[x][i]-=j,map[i][x]+=j;
			if(ret==k)	return ret;
		}
	}
	return ret;
}
int main()
{
	int m,i,j,k,x,y,ans;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		map[i<<1][i<<1|1]=m;
		map[(i+n)<<1|1][(i+n)<<1]=m;
		scanf("%s",str);
		for(j=0;j<n;j++)
			if(str[j]=='Y')
				map[i<<1][(j+1+n)<<1]=1;
			else
				map[i<<1|1][(j+1+n)<<1|1]=1;
	}
	ans=n,tot=(n<<1)<<1|1;
	for(k=0;ans==n;k++)
	{
		ans=0;
		init();
		while(bfs())
		{
			while(j=dfs(0,0x3f3f3f3f))
				ans+=j;
		}
	}
	printf("%d",k-1);
	return 0;
}