首页 > 代码库 > BZOJ1305: [CQOI2009]dance跳舞

BZOJ1305: [CQOI2009]dance跳舞

2024-07-17 17:21:35   225人阅读

1305: [CQOI2009]dance跳舞

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

题解：
我是这样想的：
1.因为有和不喜欢的人跳舞，还有和喜欢的人跳舞，所以应该把每个点拆成两个 num[i,1],num[i,2]
2.如果男生i 喜欢 女生 j，那我们连边num[i,1]到num[j,1]否则我们连边 num[i,2]到num[j,2]
3.因为每次都必须有n对，才能算一首曲子，所以我们从小到大枚举答案，当然不用重构图
   每次给每个人只加1的流量，如果某一次发现maxflow<n就退出出，输出 i-1
   至于选择不喜欢的人还是喜欢的人，由最大流决定，所以我们还得应增一个点num[i,3]，由它向num[i,1]连容量为inf的边，num[i,2]连容量为k的边
   每次枚举答案的时候由 s向num[i,3]（男生）连边，num[i,3]（女生）向t连边
4.也就是说num[i,3]是用来限制每一次的流量，必须使得一个男生只能跳一次，一个女生只能和一个男生跳
5. 至于到了下一次的时候上一次新添的边是否应该回边无效化，我也不知道，无效和不无效都能A
代码：
  1 const inf=maxlongint;maxn=5000;maxm=500000;  2 type node=record  3      from,go,next,v:longint;  4      end;  5 var  tot,i,j,n,m,maxflow,l,r,s,t,x,y,cnt:longint;  6      h,head,q,cur:array[0..2*maxn] of longint;  7      e:array[0..2*maxm] of node;  8      num:array[0..2*maxn,1..3] of longint;  9      ch:char; 10      function min(x,y:longint):longint; 11       begin 12       if x<y then exit(x) else exit(y); 13       end; 14 procedure ins(x,y,z:longint); 15  begin 16  inc(tot); 17  e[tot].from:=x;e[tot].go:=y;e[tot].v:=z;e[tot].next:=head[x];head[x]:=tot; 18  end; 19 procedure insert(x,y,z:longint); 20  begin 21  ins(x,y,z);ins(y,x,0); 22  end; 23 function bfs:boolean; 24  var i,x,y:longint; 25  begin 26  fillchar(h,sizeof(h),0); 27  l:=0;r:=1;q[1]:=s;h[s]:=1; 28  while l<r do 29   begin 30   inc(l); 31   x:=q[l]; 32   i:=head[x]; 33   while i<>0 do 34    begin 35    y:=e[i].go; 36    if (e[i].v<>0) and (h[y]=0) then 37     begin 38      h[y]:=h[x]+1; 39      inc(r);q[r]:=y; 40     end; 41    i:=e[i].next; 42    end; 43   end; 44  exit (h[t]<>0); 45  end; 46 function dfs(x,f:longint):longint; 47  var i,y,used,tmp:longint; 48  begin 49  if x=t then exit(f); 50  used:=0; 51  i:=cur[x]; 52  while i<>0 do 53   begin 54   y:=e[i].go; 55   if (h[y]=h[x]+1) and (e[i].v<>0) then 56    begin 57    tmp:=dfs(y,min(e[i].v,f-used)); 58    dec(e[i].v,tmp);if e[i].v<>0 then cur[x]:=i; 59    inc(e[i xor 1].v,tmp); 60    inc(used,tmp); 61    if used=f then exit(f); 62    end; 63   i:=e[i].next; 64   end; 65  if used=0 then h[x]:=-1; 66  exit(used); 67  end; 68 procedure dinic; 69  var i:longint; 70  begin 71  while bfs do 72   begin 73   for i:=s to t do cur[i]:=head[i]; 74   inc(maxflow,dfs(s,inf)); 75   end; 76  end; 77 procedure init; 78  begin 79  tot:=1; 80  readln(n,m); 81  for i:=1 to 2*n do 82   begin 83    inc(cnt);num[i,1]:=cnt; 84    inc(cnt);num[i,2]:=cnt; 85    inc(cnt);num[i,3]:=cnt; 86    if i<=n then 87     begin 88     insert(num[i,3],num[i,1],inf); 89     insert(num[i,3],num[i,2],m); 90     end 91    else 92     begin 93     insert(num[i,1],num[i,3],inf); 94     insert(num[i,2],num[i,3],m); 95     end; 96   end; 97  s:=0;t:=6*n+1; 98  for i:=1 to n do 99   begin100    for j:=1 to n do101     begin102     read(ch);103     if ch=‘Y‘ then insert(num[i,1],num[j+n,1],1)104     else insert(num[i,2],num[j+n,2],1);105     end;106    readln;107   end;108  end;109 procedure main;110  begin111  for i:=1 to n+1 do112    begin113    // for j:=1 to tot do if (e[j].go=t) or (e[j].from=t) then e[j].v:=0;114     for j:=1 to 2*n do if j<=n then insert(s,num[j,3],1) else insert(num[j,3],t,1);115     maxflow:=0;116     dinic;117     if maxflow<>n then break;118    end;119  writeln(i-1);120  end;121 begin122  assign(input,‘input.txt‘);assign(output,‘output.txt‘);123  reset(input);rewrite(output);124  init;125  main;126  close(input);close(output);127 end.
View Code

 

 
 


联系
我们