本文主要是介绍【HDU4560 2013西山居复赛D】【二分答案+网络流拆点】我是歌手 安排演唱会_每人歌不同_每场歌不同_人歌匹配一次，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others) |
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<string>
#include<algorithm>
#include<time.h>
#include<bitset>
using namespace std;
void fre(){freopen("c://test//input.in","r",stdin);freopen("c://test//output.out","w",stdout);}
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T> inline void gmax(T &a,T b){if(b>a)a=b;}
template <class T> inline void gmin(T &a,T b){if(b<a)a=b;}
const int N=240,M=14000,Z=1e9+7,maxint=2147483647,ms31=522133279,ms63=1061109567,ms127=2139062143;const double eps=1e-8,PI=acos(-1.0);//.0
int casenum,casei;
int id,ST,ED;
int n,m,g,L,x,y;
int first[N],w[M],cap[M],nxt[M];
bool e[80][80];
void ins(int x,int y,int cap_)
{id++;w[id]=y;cap[id]=cap_;nxt[id]=first[x];first[x]=id;id++;w[id]=x;cap[id]=0;nxt[id]=first[y];first[y]=id;
}
int d[N];
bool bfs()
{MS(d,-1);d[ST]=0;queue<int>q;q.push(ST);while(!q.empty()){int x=q.front();q.pop();for(int z=first[x];z;z=nxt[z])if(cap[z]){int y=w[z];if(d[y]==-1){d[y]=d[x]+1;if(y==ED)return 1;q.push(y);}}}return 0;
}
int dfs(int x,int all)
{if(x==ED)return all;int use=0;for(int z=first[x];z;z=nxt[z])if(cap[z]){int y=w[z];if(d[y]==d[x]+1){int tmp=dfs(y,min(cap[z],all-use));cap[z]-=tmp;cap[z^1]+=tmp;use+=tmp;if(use==all)break;}}if(use==0)d[x]=-1;return use;
}
int dinic(int flow)
{int tmp=0;while(bfs())tmp+=dfs(ST,flow);return tmp;
}
void build(int mid)
{MS(first,0);id=1;for(int i=1;i<=m;i++)ins(n+i,n+m+i,L);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(e[i][j])ins(i,n+m+j,1);else ins(i,n+j,1);}}ST=0;ED=n+m+m+1;for(int i=1;i<=n;i++)ins(ST,i,mid);for(int i=1;i<=m;i++)ins(n+m+i,ED,mid);
}
int main()
{scanf("%d",&casenum);for(casei=1;casei<=casenum;casei++){scanf("%d%d%d%d",&n,&m,&g,&L);MS(e,0);while(g--){scanf("%d%d",&x,&y);e[x][y]=1;} int l=0;int r=m;while(l<r){int mid=(l+r+1)>>1;build(mid);if(dinic(mid*n)==mid*n)l=mid;else r=mid-1;}printf("Case %d: %d\n",casei,l);}return 0;
}
/*
【trick&&吐槽】
1，最大能安排的演唱会次数是多少呢？只看一个人，这个人最多每首歌唱一次，所以ans不会超过m。
2，网络流每次跑都要重新建图。
3，初始化是在每次建图之前都要进行的。【题意】
有n（n<=74）个歌手，有m（m<=74）种类型的歌曲。有g（g<=n*m）个擅长关系（x，y），告诉你x擅长歌曲y。
然后我们希望安排数量尽可能多场演唱会。
在每场演唱会中，每个歌手唱不同类型的歌曲。
这样可能导致有些歌手去唱他不擅长的歌曲。
对于任一种歌曲，被不合适唱的次数都不能超过L（0<=L<=n*m）。
问你最多能安排多少场演唱会。【类型】
网络流【分析】
这题涉及到分配，于是我们自然会想到网络流。不过每首歌的演唱类型有两种，处理起来很难。
因为我们先简化问题——
如果只安排每个人唱自己擅长的音乐，那么最多能安排多少场演唱会呢？
我们只要每个人向自己擅长的音乐连一条容量为1的边。然后假设安排k场演唱会的话。
我们从超级源点向每个人连容量为k的边。
然后从所有音乐向超级汇点连容量为k的边。
然后跑一遍最大流，看看是否能满足，最大流=k*n。
可以说明k是可行的，且k满足二分性质。回归问题——现在每个人还可以选择演唱自己不喜欢的音乐，
这个要怎么办呢？拆点！
我们把每首音乐拆成2个点x和y，内部连接流量为L的边。
然后如果某个人擅长这首音乐，就把这个人连向y。
如果此人不擅长这首音乐，就把这个人连向x，这样我们就会记录这首音乐被不娴熟演唱的次数。这样我们总能实现匹配关系，而且这样我们还能限制每种音乐最大被不娴熟演唱的次数。
而且通过二分（或者暴力？2333），我们还可以限制每个人表演的场次。
这样就不会有任何冲突情况出现，就可以顺利AC啦！【时间复杂度&&优化】
点数最大为n+m+m+2，大概240即可。
边数最多为(n*m+m+n+m)*2，大概14000即可。*/这篇关于【HDU4560 2013西山居复赛D】【二分答案+网络流拆点】我是歌手 安排演唱会_每人歌不同_每场歌不同_人歌匹配一次的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
