题意

一次舞会有 n 个男孩和 n 个女孩。

每首曲子开始时,所有男孩和女孩恰好配成 n 对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。

有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和 k 个不喜欢的女孩跳舞,而每个女孩也最多只愿意和 k 个不喜欢的男孩跳舞。

给出每对男孩女孩是否相互喜欢的信息,求舞会最多能有几首舞曲

思路

考虑将每个男女生拆成两个点,分别为男/女生喜欢/不喜欢。

答案不好求,但由于其满足单调性所以可以使用二分答案,问题变为问跳 a 支舞曲能不能实现,注意到 a 越大越难实现,故单调性得证。

对于每一对互相喜欢的男女,从对应的男生喜欢往女生喜欢连一条容量为 1 的边,对于互相不喜欢的,就从对应的男生不喜欢往女生不喜欢连一条容量为 1 的边。之后建立超级源点 s 和超级汇点 t,从 s 往每个男生喜欢连一条容量为 a 的边(因为最多只能跳 a 支舞曲),从每个女生喜欢往 t 连一条容量为 a 的边,最后再从每个男生喜欢往对应的男生不喜欢连一条容量为 k 的边,从每个女生不喜欢往对应的女生喜欢连一条容量为 k 的边(因为不喜欢的最多只能跳 k 次)

对于每次枚举到的 a,跑一次最大流,如果最大流刚好等于 a\times n,则说明能满足跳 a 支。

具体实现

  • 边数组要开够

  • 每次枚举到的 a 要重新初始化

剩下的没有什么了,数据范围很小,不加优化的 Dinic 跑得过去

#include <cstdio>
#include <cstring>
#include <queue>

int n,k;
const int maxn=1000;
int head[maxn],cur[maxn],to[maxn<<4],nxt[maxn<<4],c[maxn<<4],cnt;
int dep[maxn];
int s,t;
char tmp[55][55];

inline void add(int u,int v,int w)
{
    to[++cnt]=v;
    nxt[cnt]=head[u];
    c[cnt]=w;
    head[u]=cnt;
    return;
}

inline int min(int a,int b){return a<b?a:b;}

//男生喜欢 :1-n 男生不喜欢 n+1-2n 女声喜欢 2n+1-3n 女生不喜欢:3n+1-4n

void build(int a)
{
    cnt=1;
    memset(head,0,sizeof head);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(tmp[i][j]=='Y')
                add(i,2*n+j,1),add(2*n+j,i,0);
            else if(tmp[i][j]=='N')
                add(n+i,3*n+j,1),add(3*n+j,n+i,0);
        }
    for(int i=1;i<=n;i++)
        add(s,i,a),add(i,s,0),
        add(i,n+i,k),add(n+i,i,0),
        add(3*n+i,2*n+i,k),add(2*n+i,3*n+i,0),
        add(2*n+i,t,a),add(t,2*n+i,0);
}

bool bfs()
{
    memset(dep,-1,sizeof dep);
    dep[s]=0;
    std::queue<int> q;
    q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=nxt[i])
        {
            int v=to[i];
            if(c[i]>0 && dep[v]==-1)
            {
                dep[v]=dep[u]+1;
                q.push(v);
                if(v==t)
                    return 1;
            }
        }
    }
    return 0;
}

int dfs(int u,int sum)
{
    if(u==t)
        return sum;
    int k,res=0;
    for(int i=head[u];i && sum;i=nxt[i])
    {
        int v=to[i];
        if(c[i]>0 && dep[v]==dep[u]+1)
        {
            k=dfs(v,min(sum,c[i]));
            if(!k)
                dep[v]=-2;
            c[i]-=k;
            c[i^1]+=k;
            res+=k;
            sum-=k;
        }
    }
    return res;
}

int dinic()
{
    int ret=0;
    while(bfs())
        ret+=dfs(s,1e9);
    return ret;
}

int main()
{
    scanf("%d %d",&n,&k);
    s=4*n+1,t=4*n+2;
    for(int i=1;i<=n;i++)scanf("%s",tmp[i]+1);
    int ans,l=0,r=n;
    while(l<=r)
    {
        int mid=l+r>>1;
        build(mid);
        if(dinic()==mid*n)
            l=mid+1,ans=mid;
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年11月23日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。