bzoj千题计划130：bzoj1305: [CQOI2009]dance跳舞

2023-07-16 21:12:57

http://www.lydsy.com/JudgeOnline/problem.php?id=1305

每个人拆为喜欢（yes）和不喜欢（no)两个点

二分答案

1、每两个人之间只能跳一次

喜欢则男yes i 向女yes j 连流量为1的边

不喜欢则男no i 向女no j 连流量为1的边

2、最多与k个不喜欢的人跳

男yes i 向男no i 连流量为 k的边

女no j 向女yes j 连流量为k 的边

3、

源点向男yes i 连流量mid 的边

女yes j 向汇点连流量为mid的边

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

#define N 2501

#define M 3001

int n,k;

char s[];

bool mp[][];

int tot;

int front[N],to[M<<],nxt[M<<],val[M<<];

int src,decc;

int cur[N],lev[N];

queue<int>q;

void read(int &x)

{

    x=;  char c=getchar();

    while(!isdigit(c)) c=getchar();

    while(isdigit(c)) { x=x*+c-''; c=getchar();  }

}

void add(int u,int v,int w)

{

    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; val[tot]=w;

    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; val[tot]=;

}

void rebuild(int mid)

{

    tot=;

    memset(front,,sizeof(front));

    for(int i=;i<=n;++i)

        for(int j=;j<=n;++j)

            if(mp[i][j]) add(i,n*+j,);

            else add(n+i,n*+j,);

    for(int i=;i<=n;++i) add(src,i,mid);

    for(int i=;i<=n;++i) add(n*+i,decc,mid);

    for(int i=;i<=n;++i) add(i,n+i,k);

    for(int i=;i<=n;++i) add(n*+i,n*+i,k);

}

bool bfs()

{

    while(!q.empty()) q.pop();

    for(int i=src;i<=decc;i++) lev[i]=-,cur[i]=front[i];

    lev[src]=;

    q.push(src);

    int now;

    while(!q.empty())

    {

        now=q.front(); q.pop();

        for(int i=front[now];i;i=nxt[i])

        {

            if(lev[to[i]]==-&&val[i]>)

            {

                lev[to[i]]=lev[now]+;

                if(to[i]==decc) return true;

                q.push(to[i]);

            }

        }

    }

    return false;

}

int dinic(int now,int flow)

{

    if(now==decc) return flow;

    int rest=,delta;

    for(int &i=cur[now];i;i=nxt[i])

    {

        if(lev[to[i]]>lev[now]&&val[i]>)

        {

            delta=dinic(to[i],min(flow-rest,val[i]));

            if(delta)

            {

                val[i]-=delta; val[i^]+=delta;

                rest+=delta; if(rest==flow) break;

            }

        }

    }

    if(rest==flow) lev[now]=-;

    return rest;

}

bool check(int mid)

{

    rebuild(mid);

    int maxflow=;

    while(bfs())

    maxflow+=dinic(src,2e9);

    return maxflow==n*mid;

}

int main()

{

    read(n); read(k);

    decc=n*+;

    for(int i=;i<=n;++i)

    {

        scanf("%s",s+);

        for(int j=;j<=n;++j) mp[i][j]=s[j]=='Y' ? true : false;

    }

    int l=,r=n,mid,ans;

    while(l<=r)

    {

        mid=l+r>>;

        if(check(mid)) ans=mid,l=mid+;

        else r=mid-;

    }

    cout<<ans;

}

1305: [CQOI2009]dance跳舞

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 3691 Solved: 1565
[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

HINT

N<=50 K<=30

码农公寓