题面见 https://www.luogu.org/problemnew/show/P3153
题意简述: 有 n 个男生, n 个女生, 每一首歌时两位男女配对, 然后同一对男女只能跳一场, 一个人只会与不喜欢的人跳 k 场, 求最大可以满员跳几场
这个题目看完可以猜测到这道题需要二分答案进行 check()
然后就是建图, 首先在 check 的时候查看是否所有边都流满了, 其次因为一对男女跳一场, 所以建边容量为 1, 然后男生和女生分别向原点和汇点连容量为 mid 的边
最后就是如何实现与不喜欢的人跳 k 场, 根据网络流的常规操作, 拆个点就很不错, 这个时候可以选择这样拆点把一个人拆成两个分点, 一个总点, 一个总点代表有 mid 流量进来, 两个分点分别和喜欢还有不喜欢的人相连, 总点向不喜欢的人连 k 容量, 向喜欢的连 mid 容量, 然后分点分别与喜欢和不喜欢相连
(我最后改成了把喜欢的分点合并到总点里面去)
然后就是代码了
- // luogu-judger-enable-o2
- #include<bits/stdc++.h>
- #include<queue>
- using namespace std;
- #define INF 0x3f3f3f3f
- inline int read(){
- int w=0,f=1;
- char ch=getchar();
- while(ch<'0'||ch>'9'){
- if(ch=='-') f=-1;
- ch=getchar();
- }
- while(ch>='0'&&ch<='9'){
- w=(w<<3)+(w<<1)+ch-48;
- ch=getchar();
- }
- return w*f;
- }
- int n,m,cur[100010],head[100010],cnt=1,depth[100010],maxflow,S,T;
- bool debug;
- const int p=1000;
- struct Edge{
- int from,to,flow,dis,next;
- }edge[5000010];
- queue<int> q;
- inline void addedge(int u,int v,int w){
- cnt++;
- edge[cnt].from=u;
- edge[cnt].to=v;
- edge[cnt].flow=w;
- edge[cnt].next=head[u];
- head[u]=cnt;
- }
- inline void ins(int u,int v,int w){
- addedge(u,v,w);addedge(v,u,0);
- }
- int mapp[110][110];
- inline bool bfs(int st,int ed){
- memset(depth,0,sizeof(depth));int i,j,k;
- for(i=0;i<=10010;i++) cur[i]=head[i];
- depth[st]=1;q.push(st);
- while(!q.empty()){
- int u=q.front();q.pop();
- for(i=head[u];i;i=edge[i].next){
- int v=edge[i].to;
- if(!depth[v]&&edge[i].flow){
- q.push(v);depth[v]=depth[u]+1;
- }
- }
- }
- return depth[ed];
- }
- inline int dfs(int u,int ed,int limit){
- if(u==ed||!limit) return limit;
- int f,i,j,k;int flow=0;
- for(i=cur[u];i;i=edge[i].next){
- cur[u]=i;int v=edge[i].to;
- if(depth[v]==depth[u]+1&&(f=dfs(v,ed,min(limit,edge[i].flow)))){
- limit-=f;flow+=f;
- edge[i].flow-=f;edge[i^1].flow+=f;
- if(!limit) break;
- }
- }
- return flow;
- }
- inline void Dinic(){
- while(bfs(S,T)){
- //cout<<"fuck1"<<endl;
- maxflow+=dfs(S,T,INF);
- }
- }
- inline bool check(int a){
- S=0;T=10000;int i,j,k;cnt=1;maxflow=0;
- memset(head,0,sizeof(head));
- for(i=1;i<=n;i++){
- ins(S,i,a);
- ins(i,i+n,m);
- ins(i+2*n,i+3*n,m);
- ins(i+3*n,T,a);
- }
- for(i=1;i<=n;i++){
- for(j=1;j<=n;j++){
- if(mapp[i][j]) ins(i,j+3*n,1);
- else ins(i+n,j+2*n,1);
- }
- }
- Dinic();
- //cout<<a<<" "<<maxflow<<endl;
- if(maxflow==a*n) return true;
- else return false;
- }
- int main(){
- n=read();m=read();int i,j,k;
- for(i=1;i<=n;i++){
- for(j=1;j<=n;j++){
- char ch;cin>>ch;
- if(ch=='Y') mapp[i][j]=1;
- else mapp[i][j]=0;
- }
- }
- int l=0,r=n+m;int ans;
- while(l<=r){
- int mid=(l+r)>>1;
- //cout<<mid<<" "<<check(mid)<<endl;
- if(check(mid)) l=mid+1,ans=mid;
- else r=mid-1;
- }
- cout<<ans<<endl;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2973523.html