使用最大流和费用流解决二分图的多重匹配
之前编辑的忘存了好气啊。。
本来打算学完二分图的乱七八糟的匹配之后再去接触网络流的，提前撞到了
之前我们说的二分图最大匹配和二分图最大权匹配有一个特点，那就是没个点只能与一条边相匹配
如果规定一个点要与L条边相匹配，这样的问题就是二分图的多重匹配问题
然后根据边是否带权重，又可以分为二分图最大多重匹配和二分图最大权多重匹配（二分图多重最佳完美匹配）
首先给出二分图多重最大匹配的做法：
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值的边，每个Y方点向T连一条容量为该Y方点L值的边
原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），求该网络的最大流，就是该二分图多重最大匹配的值
然后给出二分图多重最优匹配（二分图多重最大权匹配）的做法：
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值、费用为0的边，每个Y方点向T连一条容量为该Y方点L值、费用为0的边
原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），费用为该边的权值。求该网络的最大费用最大流，就是该二分图多重最优匹配的值
这道题里面，一共有X方点这么多的电影，每个电影需要拍摄多少天就是对应的X方点L值，然后每一天是一个Y方点，由于每一天只能拍摄一部电影，所有Y方点的L值均为1
下面介绍一下实现：
int n,sum,cnt,ans;int g[maxn],cur[maxn];int str[25][10];struct Edge{ int u,v,next,cap,flow;}e[maxm]; 这里面的cur数组是g数组的临时数组
str用来保存每一个电影可以在哪一天拍摄
Edge是网络流图里面的边
void addedge(int u,int v,int c){ e[++cnt].u=u;e[cnt].v=v;e[cnt].cap=c; e[cnt].flow=0;e[cnt].next=g[u];g[u]=cnt; e[++cnt].u=v;e[cnt].v=u;e[cnt].cap=0; e[cnt].flow=0;e[cnt].next=g[v];g[v]=cnt;} 建图的时候，注意怎么赋值的
接下来根据题意建图：
for(int i=1;i<=n;i++) { for(int j=1;j<=7;j++) scanf("%d",&str[i][j]); scanf("%d%d",&d,&w); sum+=d; addedge(0,i,d); //容量为需要多少天 for(int j=1;j<=7;j++) for(int k=0;k 0为源点，371为汇点
sum最后进行一个统计，和源点出发的最大流量进行比较，如果相等，说明电影排的开
然后是求最大流的一个板子
int maxflow(int st,int ed){ int flowsum=0; while(bfs(st,ed)) { memcpy(cur,g,sizeof(g)); flowsum+=dfs(st,ed,INF); //cout<<"#"< <<" "; } return flowsum; } 具体的DFS和BFS这里不作为重点，以后再说
下面给出完整的实现：
1 #include2 #include 3 #include 4 using namespace std; 5 const int INF=1000000000; 6 const int maxn=1005; 7 const int maxm=20005; 8 int n,sum,cnt,ans; 9 int g[maxn],cur[maxn]; 10 int str[25][10]; 11 struct Edge{ int u,v,next,cap,flow;}e[maxm]; 12 void addedge(int u,int v,int c) 13 { 14 e[++cnt].u=u;e[cnt].v=v;e[cnt].cap=c; 15 e[cnt].flow=0;e[cnt].next=g[u];g[u]=cnt; 16 17 e[++cnt].u=v;e[cnt].v=u;e[cnt].cap=0; 18 e[cnt].flow=0;e[cnt].next=g[v];g[v]=cnt; 19 } 20 int q[maxn],vis[maxn],d[maxn]; 21 bool bfs(int st,int ed) 22 { 23 memset(q,0,sizeof(q)); 24 memset(vis,0,sizeof(vis)); 25 memset(d,-1,sizeof(d)); 26 vis[st]=1;d[st]=0; 27 int h=0,t=1; 28 q[t]=st; 29 while(h!=t) 30 { 31 h=h%maxn+1; 32 int u=q[h]; 33 for(int tmp=g[u];tmp;tmp=e[tmp].next) 34 { 35 if(!vis[e[tmp].v]&&e[tmp].cap>e[tmp].flow) 36 { 37 vis[e[tmp].v]=1; 38 d[e[tmp].v]=d[u]+1; 39 if(e[tmp].v==ed) return true; 40 t=t%maxn+1; 41 q[t]=e[tmp].v; 42 } 43 } 44 } 45 return false; 46 } 47 int getpair(int x) 48 { 49 if(x%2==0) 50 return x-1; 51 else return x+1; 52 } 53 int dfs(int x,int ed,int a) 54 { 55 if(x==ed||a==0) return a; 56 int flow=0,f; 57 for(int tmp=cur[x];tmp;tmp=e[tmp].next) 58 { 59 if(d[e[tmp].v]==d[x]+1&&(f=dfs(e[tmp].v,ed,min(a,e[tmp].cap-e[tmp].flow)))>0) 60 { 61 e[tmp].flow+=f; 62 e[getpair(tmp)].flow-=f; 63 a-=f; 64 flow+=f; 65 if(a==0) break; 66 } 67 } 68 return flow; 69 } 70 int maxflow(int st,int ed) 71 { 72 int flowsum=0; 73 while(bfs(st,ed)) 74 { 75 memcpy(cur,g,sizeof(g)); 76 flowsum+=dfs(st,ed,INF); 77 //cout<<"#"< <<" "; 78 } 79 return flowsum; 80 81 } 82 void init() 83 { 84 sum=cnt=0; 85 memset(g,0,sizeof(g)); 86 } 87 int main() 88 { 89 int T,d,w; 90 scanf("%d",&T); 91 while(T--) 92 { 93 init(); 94 scanf("%d",&n); 95 for(int i=1;i<=n;i++) 96 { 97 for(int j=1;j<=7;j++) 98 scanf("%d",&str[i][j]); 99 scanf("%d%d",&d,&w);100 sum+=d;101 addedge(0,i,d); //容量为需要多少天 102 for(int j=1;j<=7;j++)103 for(int k=0;k
据说这是典型的最大流题目，然而为了强行安利一波二分图的多重匹配，就不说成那个了