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

bzoj1305[CQOI2009]dance跳舞

2024-08-13 23:25:05   218人阅读

1305: [CQOI2009]dance跳舞

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

每个点拆成喜欢和不喜欢....两人互相喜欢就喜欢的点连边  否则不喜欢的点之间连边
二分答案x
S或T和喜欢的点连边容量为x
喜欢的点向不喜欢的连边长度为k
技术分享
 1 #include<bits/stdc++.h> 2 #define N 1100 3 #define rep(i,l,r) for(int i=l;i<=r;i++) 4 #define inf 2147483647 5 using namespace std; 6 struct ndoe{ 7     int to,next,w; 8 }e[100000]; 9 int tot=1,dis[N],head[N],ans,l,r,mid,n,k,T,mp[N][N],cnt,num[N][3];10 char ch[N];11 inline void ins(int u,int v,int w) {12      e[++tot].to=v; e[tot].next=head[u]; e[tot].w=w; head[u]=tot;13 }14 inline void insert(int u,int v,int w) {15      ins(u,v,w); ins(v,u,0);16 }17 inline bool bfs(){18      for(int i=0;i<=T;i++) dis[i]=-1; queue<int>q; q.push(0); dis[0]=0;19      while(!q.empty()) {20           int x=q.front(); q.pop();21           for(int k=head[x];k;k=e[k].next) 22              if(dis[e[k].to]<0 && e[k].w>0) {23                    dis[e[k].to]=dis[x]+1; q.push(e[k].to);24              }25      }26      if(dis[T]>0) return 1;else return 0;27 }28 int find(int x,int low){29      if(x==T) return low;30      int delta=low,now;31      for(int k=head[x];k;k=e[k].next) 32        if(e[k].w>0 && dis[e[k].to]==dis[x]+1){ 33            now=find(e[k].to,min(e[k].w,delta));34            e[k].w-=now; e[k^1].w+=now;   delta-=now;35            if(!delta) return low;36         } 37      dis[x]=-1;38      return low-delta;39 }40 bool pd(int x) {41      int sum=0;42      memset(head,0,sizeof(head)); tot=1;43      rep(i,1,n) rep(j,1,n) if(!mp[i][j]) insert(num[i][1],num[j+n][1],1);44                            else insert(num[i][2],num[j+n][2],1);45      rep(i,1,n) {46          insert(num[i][0],num[i][1],k);insert(num[i][0],num[i][2],inf);47          insert(num[i+n][1],num[i+n][0],k);insert(num[i+n][2],num[i+n][0],inf);48          insert(0,num[i][0],x); insert(num[i+n][0],T,x);49      }50      while(bfs()) sum+=find(0,inf);51      if(sum==x*n) return 1;else return 0;52 }53 int main () {54      scanf("%d%d",&n,&k);55      rep(i,1,n) {56           scanf("%s",ch+1);57           rep(j,1,n) if(ch[j]==‘Y‘) mp[i][j]=1;58      }59      rep(i,1,n) rep(j,0,2) num[i][j]=++cnt,num[i+n][j]=++cnt;60      T=cnt+1;61      l=0; r=50;62      while(l<=r) {63           mid=(l+r)>>1;64          if(pd(mid)) ans=max(ans,mid),l=mid+1;else r=mid-1;65      }66      printf("%d",ans);67 }
View Code

 

bzoj1305[CQOI2009]dance跳舞


联系
我们