CQOI2009dance跳舞_cqoi2009跳舞
本文摘要: CQOI2009dance跳舞_cqoi2009跳舞,[CQOI2009]dance跳舞Description一次舞会有n个男孩和n个女孩。每首曲子开始时,所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首(或更多)舞曲。有一些男孩女孩相互喜欢,而其他相互不喜欢(不会“单向喜欢”)。每个男孩最多只愿意和k个不喜欢的女孩跳舞,而每个女孩

                                   [CQOI2009]dance跳舞


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


 


这是一道很好的二分图多重匹配的题,只是增加了一下特殊条件,用网络流来解决很方便。


通过分析题目,发现事实上,一个男孩可以和任意一个女孩跳舞,只是他喜欢的女孩不占名额,其他女孩要占K的名额。如果我们知道了每个人最多可以跳几只舞,它们之中的最小值就是答案。


建图:


1.增加源点S,向每个男孩引一条边,容量为K+他喜欢的女孩数。


2.增加汇点T,每个女孩向T引一条边,容量为K+她喜欢的男孩数。


3.每个男孩向每个女孩引一条边,容量为1。


然后求出图的最大流,每一条S向男孩的边的流量表示该男孩最多可跳的舞曲数,女孩亦然,比较出它们之中的最小值即可。



P.S. 这道题之所以可以这样做(本质就是贪心),是因为喜欢的关系是无向的,如果是有向的喜欢关系,那就要拆点,二分答案,网络流判定。

 


#include<iostream>

using namespace std;

const int oo=0x7fffffff/2;

int map[200][200]={0},save[200][200][100]={0},now[200],dis[200],fanhui[200],n,st,ar,ex,Maxflow=0,edge[1005],sumd[200],pre[200],boy[200]={0},girl[200]={0};

bool v[200]={0};

void Init()

{

     int i,j;

     char c;

     cin>>n>>ex;

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

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

       {

            cin>>c;

            boy[i]+=(c=='Y');

            girl[j]+=(c=='Y');

            map[i][j+n]=1;

            }

     st=0;ar=n*2+1;

     for( i=1;i<=n;i++)map[st][i]=boy[i]+ex,map[i+n][ar]=girl[i]+ex;

    

}

void Sap()

{

     int i,j,flow,k,Mind;

     bool flag;

     memset(dis,0,sizeof(dis));

     memset(sumd,0,sizeof(sumd));

     for( i=1;i<=n;i++)now[i]=1;

     sumd[0]=ar+1;

     i=st;

     flow=oo;

     while( dis[st]<ar+1)

     {

            fanhui[i]=flow;

           flag=0;

            for( j=now[i];j<=ar;j++)

            if( map[i][j]>0&&dis[j]+1==dis[i])

            {

                now[i]=j;

                pre[j]=i;

                flow<?=map[i][j];

                flag=1;

                i=j;

                if( i==ar)

                {

                    Maxflow+=flow;

                    while( i!=st)

                    {

                           k=pre[i];

                           map[k][i]-=flow;

                           map[i][k]+=flow;

                           i=k;

                           }

                    flow=oo;

                    }

                break;

                }

            if(flag)continue;

            Mind=ar;

            for( j=0;j<=ar;j++)

            if( map[i][j]>0&&dis[j]<Mind){now[i]=j;Mind=dis[j];}

            sumd[dis[i]]--;

            if( sumd[dis[i]]==0)break;

            dis[i]=Mind+1;

            sumd[dis[i]]++;

            if(i!=st){ flow=fanhui[i];i=pre[i];}

            }

}

void Outans()

{

     int i,Min=oo;

     for( i=1;i<=n;i++){ Min<?=boy[i]+ex-map[st][i];Min<?=girl[i]+ex-map[i+n][ar];}

     cout<<Min;

void Solve()

{

     Sap();

     Outans();

}

int main()

{

    Init();

    Solve();

     return 0;

}