二分图多重匹配问题

叁歲伎倆 2023-10-11 09:40 8阅读 0赞

解决什么问题：二分图最大匹配要求每个顶点只使用一次，即一连一。那么多重匹配就是解决一连多的问题的。比如给你n个联系人，你要把他们分在m个   　　　　　　　组里面，给你每一个联系人可以放在那个组里面。再给你一个限制条件——每个组里面最多可以放入多少人，问你可不可以分组成功

解决方法：

二分图多重匹配分为二分图多重最大匹配与二分图多重最优匹配两种，分别可以用最大流与最大费用最大流解决。

（1）二分图多重最大匹配：  
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值的边，每个Y方点向T连一条容量为该Y方点L值的边，原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），求该网络的最大流，就是该二分图多重最大匹配的值。

（2）二分图多重最优匹配：  
在原图上建立源点S和汇点T，S向每个X方点连一条容量为该X方点L值、费用为0的边，每个Y方点向T连一条容量为该Y方点L值、费用为0的边，原来二分图中各边在新的网络中仍存在，容量为1（若该边可以使用多次则容量大于1），费用为该边的权值。求该网络的最大费用最大流，就是该二分图多重最优匹配的值。

二分图多重匹配问题可以使用最大流的方法来解决，也可以使用二分图多重匹配来解决（本篇文章用二分图多重匹配来解决问题）

例题：POJ 2289

题意：

有n个人和m个小组，要求每一个人只能属于一个小组，现在已经给出每个人可以归属的小组编号（从0到M-1）。设所有小组中人数的 最多的小组所拥有的人数为num，现在让你求num最小是多少.

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<stdio.h>
     2 #include<algorithm>
     3 #include<string.h>
     4 #include<iostream>
     5 #include<queue>
     6 #include<vector>
     7 using namespace std;
     8 const int maxn=1010;
     9 int visit[maxn],maps[maxn][maxn],ans,n,m;
    10 struct shudui
    11 {
    12     int cnt;
    13     int match[maxn];
    14 }link[maxn];
    15 bool dfs_solve(int x,int limit)
    16 {
    17     for(int i=1;i<=m;++i)
    18     {
    19         if(!visit[i] && maps[x][i])
    20         {
    21             visit[i]=1;
    22             if(link[i].cnt<limit)
    23             {
    24                 link[i].match[++link[i].cnt]=x;
    25                 return 1;
    26             }
    27             for(int j=1;j<=link[i].cnt;j++)
    28             {
    29                 if(dfs_solve(link[i].match[j],limit))
    30                 {
    31                     link[i].match[j]=x;
    32                     return 1;
    33                 }
    34             }
    35         }
    36     }
    37     return 0;
    38 }
    39 bool hungran(int limit)
    40 {
    41     memset(link,0,sizeof(link));
    42     for(int i=1;i<=n;++i)
    43     {
    44         memset(visit,0,sizeof(visit));
    45         if(!dfs_solve(i,limit))
    46             return 0;
    47     }
    48     return 1;
    49 }
    50 int main()
    51 {
    52     while(~scanf("%d%d",&n,&m))
    53     {
    54         if(!n && !m) break;
    55         char s[20],ch;
    56         memset(maps,0,sizeof(maps));
    57         for(int i=1;i<=n;++i)
    58         {
    59             int x;
    60             scanf("%s",s);
    61             while(1)
    62             {
    63                 scanf("%d%c",&x,&ch);
    64                 maps[i][x+1]=1;
    65                 if(ch=='\n')
    66                     break;
    67             }
    68         }
    69         int l=1,r=n;
    70         int ans=n,mid;
    71         while(l<=r)
    72         {
    73             mid=(l+r)>>1;
    74             if(hungran(mid))
    75             {
    76                 r=mid-1;
    77                 ans=mid;
    78             }
    79             else l=mid+1;
    80         }
    81         printf("%d\n",ans);
    82     }
    83     return 0;
    84 }

可见，二分多多重匹配只是在二分图最大匹配的基础上改变了dfs\_solve()函数。多加了一个顶点连接数（只是二分图两个集合中的一个集合有），如果这个顶点(设为A集合中的顶点)的连接小于那个限制，那么就可以继续和另一个集合(设为B集合)中的顶点连接（这个集合的顶点就可以使用一次）。否则的话，就要去判断一下B集合中已经连接的点是否可以和A集合中的另一个点连接。

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11492963.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif