首页 > 代码库 > [kuangbin带你飞]专题十 匹配问题 二分图多重匹配
[kuangbin带你飞]专题十 匹配问题 二分图多重匹配
二分图的多重匹配问题不同于普通的最大匹配中的“每个点只能有最多一条边” 而是“每个点连接的边数不超过自己的限定数量”
最大匹配所解决的问题一般是“每个人都有一群想加入的团体 并且一个团体只能收一个人 问有多少人可以加入一个自己喜欢的团体”
而多重匹配是 “每个人都有一群想加入的团体 每个团体可以收给定的人数 问有多少人可以加入一个自己喜欢的团体”
解决这个问题 目前看貌似有三个办法
1 拆点 一个团体可以招x个人 就把它拆成x个只能招一个人的团体 进行最大匹配
2 网络流 s -> 人 cap : 1 人 -> 自己想加的团体 cap : 1 每个团体 -> t cap : 这个团体的容纳人数
3 改一改 xyl的形式 过去我们写linker[]来记录 每个团体的招人情况
现在我们创造一个数组 记录这个团体 能招多少人 现招多少人 招人的情况 这个网址讲的很简单 http://wenku.baidu.com/view/60b301c00c22590102029db2.html
专题里面的这三道题都差不多 都是用二分求一个最大最小值
M poj2289
模板题 需要做一个字符串处理
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , m ;
char s[1050];
struct node{
int many ;
int pp[1050];
int cnt ;
}linker[505];
bool vis[505];
vector<int >q[1050];
bool fin(int u){
for(int i = 0 ; i< q[u].size() ; i ++ ){
int v = q[u][i];
if(vis[v]){
vis[v] = false ;
if(linker[v].cnt < linker[v].many) {
linker[v].pp[++linker[v].cnt] = u ;
return true ;
}
else {
for(int j = 1; j <= linker[v].many ;j ++ ){
if(fin(linker[v].pp[j])) {
linker[v].pp[j] = u ;
return true ;
}
}
}
}
}
return false ;
}
bool xyl(int many) {
int res = 0 ;
for(int i = 0 ; i < m ; i ++) {
linker[i].many = many ;
linker[i].cnt = 0 ;
}
for(int i = 1 ; i <= n ; i ++ ){
memset(vis , true , sizeof(vis )) ;
if(fin(i)){
res ++ ;
}
}
return (res == n) ;
}
int main(){
while(scanf("%d%d\n",&n,&m)!=EOF){
if(n == 0 && m == 0)break;
for(int i = 1; i<= n ; i ++)q[i].clear() ;
for(int i = 1; i<= n ; i ++ ){
gets(s) ;
int len = strlen(s);
int j ;
for(j = 0 ; j < len ;j ++ ){
if(s[j] == ‘ ‘){
j ++ ;
break ;
}
}
int res = 0;
for( ; j < len ; j ++ ){
if(s[j ] == ‘ ‘){
q[i].push_back(res );
res = 0 ;
}
else {
res *= 10 ;
res += ( s[j] - ‘0‘ );
}
}
q[i].push_back(res);
res = 0;
}
int ans = -1 ;
int l = 1 ;
int r = 1010;
while(l <= r){
int mid = (l + r) / 2 ;
if(xyl(mid)){
ans = mid ;
r = mid - 1 ;
}
else {
l = mid + 1 ;
}
}
printf("%d\n",ans);
}
}
N poj2112
画风突然不对了 细节很多
1 给出的邻接矩阵形式 并不是最短距离 而是类似于 给出一群路来 连接每一个地点
2 给出的 0 代表这两个地点没有路
需要二分一下最大距离
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , a , b , m ;
struct node{
int many ;
int pp[300];
int cnt ;
}linker[300];
bool vis[300];
int c[300][300];
bool fin(int u , int jl){
for(int v = 1; v <= a ; v ++ ){
if(c[u][v] > jl || c[u][v] == 0){
continue ;
}
if(vis[v]){
vis[v] = false ;
if(linker[v].cnt < linker[v].many){
linker[v].pp[++linker[v].cnt] = u ;
return true ;
}
else {
for(int j = 1 ; j <= linker[v].many ; j ++ ){
if(fin(linker[v].pp[j] , jl)){
linker[v].pp[j] = u ;
return true ;
}
}
}
}
}
return false ;
}
bool xyl(int jl){
int res = 0 ;
for(int i = 1; i <= a ;i ++){
linker[i].cnt = 0 ;
linker[i].many = m ;
}
for(int i = a + 1 ; i <= n ; i ++ ){
memset(vis , true , sizeof(vis)) ;
if(fin(i , jl)){
res ++ ;
}
}
return (res == b) ;
}
int main(){
while(scanf("%d%d%d",&a , &b , & m)!= EOF){
n = a + b;
for(int i = 1; i <= n ; i ++ ){
for(int j = 1 ; j <= n ; j ++ ){
scanf("%d" , &c[i][j]) ;
}
}
for(int i = 1 ; i <= n ; i ++ ){
for(int j = 1 ; j <= n; j ++ ){
for(int k = 1; k <= n ; k ++ ){
if(i == j || i == k || k == j)continue;
if(c[j][i] != 0 && c[i][k] != 0){
if(c[j][k] > 0)
c[j][k] = min(c[j][i] + c[i][k] , c[j][k]) ;
else {
c[j][k] = c[j][i] + c[i][k] ;
}
}
}
}
}
int l = 1 ;
int r = 999999999 ;
int ans = -1 ;
while(l <= r){
int mid = (l + r) / 2 ;
if(xyl(mid)){
ans = mid ;
r = mid - 1 ;
}
else {
l = mid + 1 ;
}
}
printf("%d\n",ans) ;
}
}
O poj3189
比较考验读题能力...
题意是 给出每头牛对每个谷仓的loverank
求出一个最小的范围 让每头牛最后分配的谷仓的loverank都在这个大小范围内
所以二分范围 枚举起点
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<map>
#include<string>
#include<vector>
#include<queue>
#include<iostream>
using namespace std;
#define L long long
int n , b ;
struct node{
int many ;
int pp[1050];
int cnt ;
}linker[25];
bool vis[25];
int many[25];
int c[1050][25] ;
bool fin(int u , int jl , int st){
for(int i = st; i <= st + jl - 1; i ++ ){
int v = c[u][i] ;
if(vis[v]) {
vis[v] = false ;
if(linker[v].cnt < linker[v].many) {
linker[v].pp[++linker[v].cnt] = u ;
return true ;
}
else {
for(int j = 1 ; j <= linker[v].many ; j ++ ){
if(fin(linker[v].pp[j] , jl , st)){
linker[v].pp[j] = u ;
return true ;
}
}
}
}
}
return false ;
}
bool xyl(int jl , int st){
int res = 0 ;
for(int i = 1; i <= b ;i ++ ){
linker[i].cnt = 0;
linker[i].many = many[i] ;
}
for(int i = 1 ; i <= n ; i ++ ){
memset(vis , true , sizeof(vis)) ;
if(fin(i , jl , st)){
res ++ ;
}
}
return (res == n) ;
}
int main(){
while(scanf("%d%d",&n , &b)!=EOF){
for(int i = 1; i<= n ; i ++ ){
for(int j = 1 ; j <= b ;j ++ ){
scanf("%d" , &c[i][j]) ;
}
}
for(int i = 1; i<= b ; i ++ ){
scanf("%d" , &many[i]) ;
}
int l = 1;
int r = b ;
int ans = -1 ;
while(l <= r){
int mid = (l + r) / 2 ;
int i ;
for(i = 1; i + mid - 1 <= b ; i ++ ){
if(xyl(mid , i)){
ans = mid ;
r = mid - 1 ;
break ;
}
}
if(i + mid - 1 > b){
l = mid + 1 ;
}
}
printf("%d\n",ans) ;
}
}
可以看到Dinic跑多重匹配和跑最大匹配 都是一样的写法 只是cap不同
看起来的话 拆点法和xyl的时间复杂度都是很高的 .. Dinic不错的样子
看起来 小虎的担子 又重了一分
[kuangbin带你飞]专题十 匹配问题 二分图多重匹配
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。