「BZOJ1305」[CQOI2009] dance跳舞

2014年3月13日7,3090

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

题解

先把每个人i拆分成ix和iy两个节点，ix连向喜欢的人，iy连向不喜欢的人，容量为1（比如如果男生i与女生j互相喜欢，则由ix连向jx，如果男生i与女生j互相不喜欢，则由iy连向jy），再将每个男生男生ix连向iy，容量为k；每个女生iy连向ix，容量为k。由源点向每个男生的x节点连上一条边，再由每个女生的x节点向汇点连上一条边，容量均为a。最后从小到大枚举a，计算最大流flow，若发现a*n>flow(不满流)，则停止枚举，a-1即为答案。

或者可以二分

#include<iostream>
#include<cstdio>
#include<cstring>
#define inf 0x7fffffff
#define T 1001
using namespace std;
int head[1005],q[1005],h[1005];
int cnt,ans,mx,mid;
int n,k,mp[1005][1005];
struct data{int to,next,v;}e[500001];
void ins(int u,int v,int w)
{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,0);}
bool bfs()
{
     int t=0,w=1,i,now;
     memset(h,-1,sizeof(h));
     q[0]=0;h[0]=0;
     while(t<w)
     {
               now=q[t];t++;i=head[now];
               while(i)
               {
                       if(e[i].v&&h[e[i].to]==-1)
                       {
                                                 h[e[i].to]=h[now]+1;
                                                 q[w++]=e[i].to;
                                                 }
                       i=e[i].next;
                       }
               }
    return h[T]==-1? 0:1;
 }
int dfs(int x,int f)
{
    if(x==T)return f;
    int w,used=0,i;
    i=head[x];
    while(i)
    {
            if(e[i].v&&h[e[i].to]==h[x]+1)
            {
                                          w=f-used;
                                          w=dfs(e[i].to,min(w,e[i].v));
                                          e[i].v-=w;
                                          e[i^1].v+=w;
                                          used+=w;
                                          if(used==f)return f;
                                          }
            i=e[i].next;
            }
    if(!used)h[x]=-1;
    return used;
}
void dinic(){while(bfs())ans+=dfs(0,inf);}
void ini()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
       char ch[51];
       scanf("%s",ch);
       for(int j=1;j<=n;j++)
          if(ch[j-1]=='Y')mp[i][j]=1;
       }
}
void build()
{
    cnt=1;memset(head,0,sizeof(head));
    for(int i=1;i<=n;i++)insert(0,i,mid);
    for(int i=1;i<=n;i++)insert(i,i+500,k);
    for(int i=1;i<=n;i++)insert(n+i+500,n+i,k);
    for(int i=1;i<=n;i++)insert(n+i,T,mid);
    for(int i=1;i<=n;i++)
       for(int j=1;j<=n;j++)
          if(mp[i][j])insert(i,n+j,1);
          else insert(i+500,n+j+500,1);
}
int main()
{
    ini();int l=0,r=50;
    while(l<=r)
    {
        mid=(l+r)>>1;
        build();
        ans=0;dinic();
        if(ans>=n*mid){mx=mid;l=mid+1;}
        else r=mid-1;
    }
    printf("%d",mx);
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#define inf 0x7fffffff

#define T 1001

using namespace std;

int head[1005],q[1005],h[1005];

int cnt,ans,mx,mid;

int n,k,mp[1005][1005];

struct data{int to,next,v;}e[500001];

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

{e[++cnt].to=v;e[cnt].next=head[u];e[cnt].v=w;head[u]=cnt;}

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

{ins(u,v,w);ins(v,u,0);}

bool bfs()

{

int t=0,w=1,i,now;

memset(h,-1,sizeof(h));

q[0]=0;h[0]=0;

while(t<w)

{

now=q[t];t++;i=head[now];

while(i)

{

if(e[i].v&&h[e[i].to]==-1)

{

h[e[i].to]=h[now]+1;

q[w++]=e[i].to;

}

i=e[i].next;

}

return h[T]==-1? 0:1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0,i;

i=head[x];

while(i)

{

if(e[i].v&&h[e[i].to]==h[x]+1)

{

w=f-used;

w=dfs(e[i].to,min(w,e[i].v));

e[i].v-=w;

e[i^1].v+=w;

used+=w;

if(used==f)return f;

}

i=e[i].next;

}

if(!used)h[x]=-1;

return used;

}

void dinic(){while(bfs())ans+=dfs(0,inf);}

void ini()

{

scanf("%d%d",&n,&k);

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

{

char ch[51];

scanf("%s",ch);

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

if(ch[j-1]=='Y')mp[i][j]=1;

}

void build()

{

cnt=1;memset(head,0,sizeof(head));

for(int i=1;i<=n;i++)insert(0,i,mid);

for(int i=1;i<=n;i++)insert(i,i+500,k);

for(int i=1;i<=n;i++)insert(n+i+500,n+i,k);

for(int i=1;i<=n;i++)insert(n+i,T,mid);

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

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

if(mp[i][j])insert(i,n+j,1);

else insert(i+500,n+j+500,1);

}

int main()

{

ini();int l=0,r=50;

while(l<=r)

{

mid=(l+r)>>1;

build();

ans=0;dinic();

if(ans>=n*mid){mx=mid;l=mid+1;}

else r=mid-1;

}

printf("%d",mx);

return 0;

}

« 「网络流24题」圆桌聚餐「JoyOI1460」旅行 »

hzwer.com _ Home | http://hzwer.com

「BZOJ1305」[CQOI2009] dance跳舞

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论