【最大流】BZOJ1305-[CQOI2009]dance跳舞

【题目大意】

一次舞会有n个男孩和n个女孩。每首曲子开始时，所有男孩和女孩恰好配成n对跳交谊舞。每个男孩都不会和同一个女孩跳两首（或更多）舞曲。有一些男孩女孩相互喜欢，而其他相互不喜欢（不会“单向喜欢”）。每个男孩最多只愿意和k个不喜欢的女孩跳舞，而每个女孩也最多只愿意和k个不喜欢的男孩跳舞。给出每对男孩女孩是否相互喜欢的信息，舞会最多能有几首舞曲？

【思路】

假设当前有a首舞曲。

把每个人拆成两个点，从“喜欢”到“不喜欢”连一条容量为k的边。从S往“男孩喜欢”连一条容量为a的边，从“女孩喜欢”往T连一条容量为a的边。

然后对于每对男孩女孩，如果不喜欢，则从“男孩不喜欢”到“女孩不喜欢”连一条容量为1的边，否则从“男孩喜欢”到“女孩喜欢”连一条容量为1的边。

为什么这个是正确的呢？这样相当于喜欢的人之间限制住了至多跳一首，而最多和k个不喜欢的人跳舞。画图感受一下就好了。

如果这a首舞曲都能用到，那么这个网络流应该是满流的。

所以二分答案。

注意很重要的两点：

①二分最后ub还要单独判断一下。

②不要忘了每次E的容量会被修改，所以暂存到rE每次重新回到原始状态。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<queue>
  7 #define INF 0x7fffffff
  8 #define S 0
  9 #define T 4*n+1
 10 using namespace std;
 11 struct node
 12 {
 13     int to,pos,cap;
 14 };
 15 const int MAXN=50+5;
 16 int n,k; 
 17 vector<node> E[MAXN*4+2];
 18 vector<node> tmpE[MAXN*4+2];
 19 int dis[MAXN*4+2];
 20 
 21 void addedge(int u,int v,int w)
 22 {
 23     tmpE[u].push_back((node){v,tmpE[v].size(),w});
 24     tmpE[v].push_back((node){u,tmpE[u].size()-1,0});
 25     E[u].push_back((node){v,E[v].size(),w});
 26     E[v].push_back((node){u,E[u].size()-1,0});
 27 }
 28 
 29 bool bfs()
 30 {
 31     memset(dis,-1,sizeof(dis));
 32     queue<int> que;
 33     while (!que.empty()) que.pop(); 
 34     que.push(S);
 35     dis[S]=0;
 36     while (!que.empty())
 37     {
 38         int head=que.front();que.pop();
 39         if (head==T) return true;    //首次抵达T即可返回，不需要整张图全部分层 
 40         for (int i=0;i<E[head].size();i++)
 41         {
 42             node tmp=E[head][i];
 43             if (dis[tmp.to]==-1 && tmp.cap)
 44             {
 45                 dis[tmp.to]=dis[head]+1;
 46                 que.push(tmp.to);
 47             }
 48         }
 49     }
 50     return false;
 51 }
 52  
 53 int dfs(int s,int e,int f)
 54 {
 55     if (s==e) return f;
 56     int ret=0;
 57     for (int i=0;i<E[s].size();i++)
 58     {
 59         node &tmp=E[s][i];
 60         if (dis[tmp.to]==dis[s]+1 && tmp.cap)
 61         {
 62             int delta=dfs(tmp.to,e,min(f,tmp.cap));
 63             if (delta>0)
 64             {
 65                 tmp.cap-=delta;
 66                 E[tmp.to][tmp.pos].cap+=delta;
 67                 f-=delta;
 68                 ret+=delta;
 69                 if (f==0) return ret;
 70             }
 71             else dis[tmp.to]=-1;
 72         }
 73     } 
 74     return ret;
 75 }
 76  
 77 int dinic()
 78 {
 79     int flow=0;
 80     while (bfs())
 81     {
 82         int f=dfs(S,T,INF);
 83         if (f) flow+=f;else break;
 84     }
 85     return flow;
 86 }
 87 
 88 void init()
 89 {
 90     scanf("%d%d",&n,&k);
 91 //0 源点  
 92 //1～n 男性喜欢  
 93 //n+1~2n 男性不喜欢  
 94 //2n+1~3n 女性不喜欢  
 95 //3n+1~4n 女性喜欢  
 96 //4n+1 汇点  
 97     for (int i=1;i<=n;i++) addedge(i,i+n,k);
 98     for (int i=2*n+1;i<=3*n;i++) addedge(i,i+n,k);
 99     for (int i=1;i<=n;i++)
100     {
101         char str[MAXN];
102         scanf("%s",str+1);
103         for (int j=1;j<=n;j++)
104         {
105             if (str[j]=='Y') addedge(i,3*n+j,1);
106                 else addedge(n+i,2*n+j,1); 
107         } 
108     }
109     for (int i=1;i<=n;i++) addedge(S,i,0);
110     for (int i=3*n+1;i<=4*n;i++) addedge(i,T,0);
111 }
112 
113 void solve()
114 {
115     int lb=0,ub=n;
116     while (lb+1<ub)
117     {
118         for (int i=S;i<=T;i++)
119             for (int j=0;j<E[i].size();j++) E[i][j]=tmpE[i][j];
120         int mid=(lb+ub)>>1;
121         for (int i=0;i<n;i++) E[S][i].cap=mid;
122         for (int i=3*n+1;i<=4*n;i++) E[i][E[i].size()-1].cap=mid;
123         int d=dinic();
124         if (d==mid*n) lb=mid;else ub=mid;
125     }
126     for (int i=S;i<=T;i++)
127         for (int j=0;j<E[i].size();j++) E[i][j]=tmpE[i][j];
128     for (int i=0;i<n;i++) E[S][i].cap=ub;
129     for (int i=3*n+1;i<=4*n;i++) E[i][E[i].size()-1].cap=ub;
130     int d=dinic();
131     printf("%d",(d==ub*n)?ub:lb);
132 }
133 
134 int main()
135 {
136     init();
137     solve();
138     return 0;
139 }