跟随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;

}