题解 - P3153 [CQOI2009]跳舞

· · 个人记录 

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

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

输出格式：
仅一个数，即舞曲数目的最大值。

输入输出样例
输入样例#1： 
3 0
YYY
YYY
YYY
输出样例#1： 
3
说明
N<=50 K<=30

思路：

我们一个一个分析：

  1. 都要跳舞

既然不能干看着，那么一首舞曲中，每个人都得跳，换言之，若是本题答案为ans，那么最终每人都能跳ans只舞，

所以我们二分答案，在某个模型下跑最大流，最后检查答案，若满足条件：（跳舞的总数就是ans * N（人数））我们就往上搜，否则就往下搜，不断缩小二分范围，找到答案 （其实貌似数据范围可以直接枚举）

  1. 不会和同一人跳舞

匹配的基本知识，男女连边容量为1即可，不再赘述

  1. 能和k个不喜欢的人跳舞

我们要求能跳舞的场数最多，自然就想k尽可能多一点，虽然k是不能改变的，但是依据贪心的思想，我们能不用k就尽量不用k，换言之，如果和舞伴互相喜欢，就不用消耗k的次数了。

说明一下，入边都是k，出边也是k，如何证明一定存在合法方案，hull定理：二分图中，任意k的点有不同的任意k的连边，可以构造出一个完美匹配。于是每个点出k条，任意x个点，有kx条边，右侧每个点最多接受k条，所以至少有k个不同的点。我们取这一种完美匹配。转化成出入边都有（k-1）条，同理构造即可。

于是二分加网络流判断就好了。（记得初始化）

code

#include<bits/stdc++.h>
using namespace std;
int a[100][100],head[500005],nex[500005],go[500005],w[500005],k,n,d,l,r,mid,S,T,bi=1,lev[500005],cnt[500005];
void add(int x,int y,int z)
{
    nex[++bi]=head[x];
    head[x]=bi;
    go[bi]=y;
    w[bi]=z;
}
int dfs(int u,int flow)
{
    if(u==T)
    return flow;
    int res=0,sum=0;
    for(int i=head[u];i;i=nex[i])
    {
        int v=go[i];
        if(w[i]&&lev[u]==lev[v]+1)
        {
            sum=dfs(v,min(flow-res,w[i]));
            if(sum)
            {
                w[i]-=sum;
                w[i^1]+=sum;
                res+=sum;
            }
        }
        if(res==flow) return flow;
    }
    if(--cnt[lev[u]]==0)
    lev[S]=T+1;
    ++cnt[++lev[u]];
    return res;
}
void bfs()
{
    memset(lev,-1,sizeof(lev));
    memset(cnt,0,sizeof(cnt));
    cnt[0]=1;
    queue <int> q;
    q.push(T);
    lev[T]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nex[i])
        {
            int v=go[i];
            if(lev[v]==-1)
            {
                cnt[lev[v]=lev[u]+1]++;
                q.push(v);
            }
        }
    }
}
int pd(int x)
{
    bi=1;
    memset(head,0,sizeof(head));//注意清零
    for(int i=1;i<=n;i++)
    {
        add(i,i+n,k);//不喜欢限制
        add(i+n,i,0);
        add(i+3*n,i+2*n,k);
        add(i+2*n,i+n*3,0);
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==1)
            {
                add(i,j+n*2,1);//一对只能匹配一次，连1的边
                add(j+n*2,i,0);
            }
            else{
                add(n+i,j+3*n,1);
                add(j+3*n,i+n,0);
            }
        }
    }
    for(int i=1;i<=n;i++) 
    {
        add(0,i,x);
        add(i,0,0);
        add(i+2*n,T,x);//处理起点终点
        add(T,i+n*2,0);
    }
    long long ans=0;
    bfs();
    while(lev[S]<T)
    {
        ans+=dfs(S,1e9);
    }
    //cout<<ans<<endl;
    if(ans==x*n)
    return 1;
    return 0;
}
signed main()
{
    cin>>n>>k;
    char ss[100][100];
    for(int i=1;i<=n;i++)
    {
        scanf("%s",ss[i]+1);
        for(int j=1;j<=n;j++)
        {
            if(ss[i][j]=='Y')
            {
                a[i][j]=1;
            }
        }
    }
  //  cout<<endl<<endl<<endl;
    l=1,r=n;
    S=0;
    T=4*n+1;
    while(l<=r)
    {
        int mid=l+r>>1;
        if(pd(mid))
        l=mid+1;
        else{
            r=mid-1;
        }
    }
    cout<<l-1;
    return 0;   
}