跟随YveH的脚步又做了道网络流。。。%%%
1305: [CQOI2009]dance跳舞
Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 2119 Solved: 878
[Submit][Status][Discuss]
Description
一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？
Input
第一行包含两个整数n和k。以下n行每行包含n个字符，其中第i行第j个字符为’Y’当且仅当男孩i和女孩j相互喜欢。
Output
仅一个数，即舞曲数目的最大值。
Sample Input
3 0
YYY
YYY
YYY
Sample Output
3
HINT
N<=50 K<=30
Source
加强数据By dwellings and liyizhen2
这道题，网上有说可以贪心的，然而似乎被证明是错误的了，（反正我也想不出贪心策略）
说一下建图：（建图有点麻烦，多谢恒妹的查错）
每个男孩建立两个次节点，每个女孩建立两个次节点，分别处理喜欢的和不喜欢的
超级源S向所有男生主节点连边，所有女生向超级汇连边，边权为二分枚举出来的值
男生主节点和处理喜欢的男生次节点连边边权为INF，向处理不喜欢的男生连边边权为k
女生处理喜欢的次节点向主节点连边，边权INF；处理不喜欢的次节点与主节点相连边权为k
相互喜欢的男生女生的喜欢节点相连边权为1，相互不喜欢的连边，边权为1
二分答案，及超级源指向男生主节点的边权（女生主节点指向超级汇的边权）
每次二分出答案重新建图，跑一边Dinic判断是否满流，最后输出二分出边权即可。
（这道题目不错不错）
（一开始没写二分写了个枚举，结果卡常了。。。“竟然被卡常了，666啊”—by YveH）
code：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int q[3000],h,t;
struct data{
int to,next,v;
}edge[1000001];
int cnt;
int head[3000]={0};
int dis[3000]={0};
int xh[51][51];
int n,k,num;
void add(int u,int v,int w)
{
cnt++;
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
edge[cnt].v=w;
}
void init()
{
scanf("%d%d",&n,&k);
for (int i=1; i<=n; i++)
{
char x[51];
scanf("%s",&x);
for (int j=1; j<=n; j++)
if (x[j-1]=='Y')
xh[i][j]=1;
}
}
void make(int v)
{
//男生i的主点序号为 in 则处理喜欢的次点序号为in+1，处理不喜欢的次点序号为in+2
//女生同理，接男生后面排
//超级源的序号0，超级汇为2*n*3+1
cnt=1; memset(head,0,sizeof(head));
num=1;
for (int i=1; i<=n; i++)
{
add(0,num,v);add(num,0,0);
num++;
add(num-1,num,0x7fffffff);add(num,num-1,0);
num++;
add(num-2,num,k);add(num,num-2,0);
num++;
}
for (int i=1; i<=n; i++)
{
add(num,2*n*3+1,v);add(2*n*3+1,num,0);
num++;
add(num,num-1,0x7fffffff);add(num-1,num,0);
num++;
add(num,num-2,k);add(num-2,num,0);
num++;
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=n; j++)
{
if (xh[i][j]==1)
{
add(i*3-2+1,3*n+j*3-2+1,1);
add(3*n+j*3-2+1,i*3-2+1,0);
}
else
{
add(i*3-2+2,3*n+j*3-2+2,1);
add(3*n+j*3-2+2,i*3-2+2,0);
}
}
}
}
bool bfs()
{
memset(dis,-1,sizeof(dis));
q[1]=0; dis[0]=1;
h=0; t=1;
while (h<t)
{
int j=q[++h],i=head[j];
while (i)
{
if (edge[i].v>0 && dis[edge[i].to]<0)
{
dis[edge[i].to]=dis[j]+1;
q[++t]=edge[i].to;
}
i=edge[i].next;
}
}
if (dis[num]>0)
return true;
else
return false;
}
int dfs(int loc,int low)
{
int now=0;
if (loc==num) return low;
int i=head[loc];
while (i)
{
if (edge[i].v>0 && dis[edge[i].to]==dis[loc]+1 && (now=dfs(edge[i].to,min(edge[i].v,low))))
{
edge[i].v-=now;
edge[i^1].v+=now;
return now;
}
i=edge[i].next;
}
return 0;
}
int main()
{
init();
int ans;
int flow;
int l=0,r=50;
while (l<=r)
{
int mid=(l+r)>>1;
make(mid);
flow=0;
while (bfs())
{
int now=0;
while ((now=dfs(0,0x7fffffff)))
flow+=now;
}
if (mid*n<=flow)
{l=mid+1;ans=mid;}
else
r=mid-1;
}//二分判断是否满流
printf("%d",ans);
return 0;
}