bzoj 1305: [CQOI2009]dance 二分+網絡流判定

1305: [CQOI2009]dance跳舞

Time Limit: 5 Sec  Memory Limit: 162 MB
Submit: 1340  Solved: 581
[Submit][Status]

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

這道題知道是二分+網絡流後，就是完完全全的水題了。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<ctime>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<string>

#include<queue>

using namespace std;

#ifdef WIN32

#define LL "%I64d"

#else

#define LL "%lld"

#endif

#define MAXN 55

#define MAXV MAXN*MAXN*2

#define MAXE MAXV*2

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3fLL

typedef long long qword;

inline int nextInt()

{

        char ch;

        int x=;

        bool flag=false;

        do

                ch=getchar(),flag=(ch=='-')?true:flag;

        while(ch<''||ch>'');

        do x=x*+ch-'';

        while (ch=getchar(),ch<='' && ch>='');

        return x*(flag?-:);

}

int n,m;

char mp[MAXN][MAXN];

struct Edge

{

        int val,np;

        Edge *next,*neg;

}E[MAXE],*V[MAXV];

int tope=;

int sour=,sink=;

inline void addedge(int x,int y,int z)

{

        //cout<<"Add edge:<"<<tope+1<<">"<<x<<" "<<y<<":"<<z<<endl;

        E[++tope].np=y;

        E[tope].val=z;

        E[tope].next=V[x];

        V[x]=&E[tope];

        E[++tope].np=x;

        E[tope].val=;

        E[tope].next=V[y];

        V[y]=&E[tope];

        E[tope].neg=&E[tope-];

        E[tope-].neg=&E[tope];

}

int q[MAXV],lev[MAXV];

int vis[MAXV],bfstime=;

bool bfs()

{

        int i,j;

        int head=-,tail=;

        Edge *ne;

        lev[sour]=;

        vis[sour]=++bfstime;

        q[]=sour;

        while (head<tail)

        {

                for (ne=V[q[++head]];ne;ne=ne->next)

                {

                        if (!ne->val || vis[ne->np]==bfstime)continue;

                        q[++tail]=ne->np;

                        vis[ne->np]=bfstime;

                        lev[ne->np]=lev[q[head]]+;

                }

        }

        return vis[sink]==bfstime;

}

int dfs(int now,int maxf)

{

        int ret=,t;

        if (now==sink || !maxf)return maxf;

        Edge* ne;

        for (ne=V[now];ne;ne=ne->next)

        {

                if (!ne->val || lev[ne->np]!=lev[now]+)continue;

                t=dfs(ne->np,min(maxf,ne->val));

                ne->val-=t;

                ne->neg->val+=t;

                maxf-=t;

                ret+=t;

                //cout<<"Flow:"<<now<<"-"<<ne->np<<":"<<x<<"("<<ne->val<<")"<<endl;

        }

        if (!ret)lev[now]=-;

        return ret;

}

int dinic()

{

        int ret=;

        while (bfs())

        {

                ret+=dfs(sour,INF);

        }

        return ret;

}

int main()

{

        freopen("input.txt","r",stdin);

        //freopen("output.txt","w",stdout);

        int i,j,k;

        int x,y,z;

        scanf("%d%d\n",&n,&m);

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

        {

                fgets(mp[i],MAXN,stdin);

        }

        int ans=;

        int l=,r=n+,mid;

        while (l+<r)

        {

                memset(V,,sizeof(V));

                tope=-;

                mid=(l+r)>>;

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

                {

                        addedge(sour,+i,mid);

                        addedge(+i,+i+n*,m);

                        addedge(+i+n,sink,mid);

                        addedge(+i+n+n*,+i+n,m);

                }

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

                {

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

                        {

                                if (mp[i][j]!='Y')

                                {

                                        addedge(+i+n*,+n+j+n*,);

                                }else

                                {

                                        addedge(+i,+j+n,);

                                }

                        }

                }

                ans=dinic();

                if (ans!=mid*n)

                {

                        r=mid;

                }else

                {

                        l=mid;

                }

        }

        printf("%d\n",l);

        return ;

}