图论3 二分图匹配

2018-06-17 22:51:02来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

可以先在这里学学http://www.renfei.org/blog/bipartite-matching.html

模板

据上面的博客可知,二分图匹配可以分4种类型

最大匹配数:最大匹配的匹配边的数目

最小点覆盖数:选取最少的点,使任意一条边至少有一个端点被选择

最大独立数:选取最多的点,使任意所选两点均不相连

最小路径覆盖数:对于一个 DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为 0(即单个点)。

定理1:最大匹配数 = 最小点覆盖数(这是 Konig 定理)

定理2:最大匹配数 = 最大独立数

定理3:最小路径覆盖数 = 顶点数 - 最大匹配数

1.最大匹配数

最大匹配的匹配边的数目

洛谷P3386 【模板】二分图匹配

 P3386 【模板】二分图匹配
难度 提高+/省选-
题目背景

二分图

题目描述

给定一个二分图,结点个数分别为n,m,边数为e,求二分图最大匹配数

输入输出格式

输入格式:
第一行,n,m,e

第二至e+1行,每行两个正整数u,v,表示u,v有一条连边

输出格式:
共一行,二分图最大匹配

输入输出样例

输入样例#11 1 1
1 1
输出样例#11
说明

n,m<=10001<=u<=n,1<=v<=m

因为数据有坑,可能会遇到v>m的情况。请把v>m的数据自觉过滤掉。

算法:二分图匹配
题目描述
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxm 100010
#define maxn 1010
using namespace std;
int n,m,E,num,head[maxm],link[maxn],vis[maxn],sum;
struct node{
    int to,pre;
}e[maxm];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
int dfs(int x){
    for(int i=head[x];i;i=e[i].pre){
        int v=e[i].to;vis[v]=1;
        if(link[v]==0||dfs(link[v])){
            link[v]=x;return 1;
        }
    }return 0;
}
int main(){
    scanf("%d%d%d",&n,&m,&E);
    int x,y;
    for(int i=1;i<=E;i++){
        scanf("%d%d",&x,&y);
        Insert(x,y+n);
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))sum++;
    }
    printf("%d",sum);
}
边表 RE+MLE
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1010
using namespace std;
int n,m,e,link[maxn],re[maxn][maxn],vis[maxn],ans;
int dfs(int x){
    for(int i=1;i<=m;i++)
        if(vis[i]==0&&re[x][i]){
            vis[i]=1;
            if(link[i]==0||dfs(link[i])){
                link[i]=x;return 1;
            }
        }
    return 0;
}
int main(){
    scanf("%d%d%d",&n,&m,&e);
    int x,y;
    for(int i=1;i<=e;i++){
        scanf("%d%d",&x,&y);
        re[x][y]=1;
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }
    printf("%d",ans);
}
邻接矩阵 AC
#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#define INF 1e9
#define maxn 100008
using namespace std;
int num=1,head[maxn];
struct node{
    int to,pre,flow;
}e[maxn<<5];
int d[maxn],s,t,th[maxn];
void Insert(int from,int to,int v){
    e[++num].to=to;
    e[num].flow=v;
    e[num].pre=head[from];
    head[from]=num;
}
bool bfs(){
    queue<int>q;q.push(s);int now;
    memset(d,-1,sizeof(d));d[s]=0;
    while(!q.empty()){
        now=q.front();q.pop();
        for(int i=head[now];i;i=e[i].pre){
            int to=e[i].to;
            if(e[i].flow&&d[to]<0){
                d[to]=d[now]+1;
                if(to==t)return 1;
                q.push(to);
            }
        }
    }
    if(d[t]==-1)return 0;
    return 1;
}
int flowing(int now,int f){
    if(f<=0||now==t)return f;
    int r=0,p,v;
    for(int i=th[now];i;i=e[i].pre){
        int to=e[i].to;
        if(!e[i].flow||d[to]!=d[now]+1)continue;
        p=flowing(to,min(e[i].flow,f));
        e[i^1].flow+=p,e[i].flow-=p;r+=p;f-=p;
        if(f<=0)return r;
    }
    if(r!=f)d[now]=-1;return r;
}
int main(){
    freopen("Cola.txt","r",stdin); 
    int n,m,E,x,y,ans=0;
    scanf("%d%d%d",&n,&m,&E);
    for(int i=1;i<=E;i++){
        scanf("%d%d",&x,&y);
        if(x>m||y>m)continue;
        Insert(x,y+n,1);Insert(y+n,x,0);
    }
    t=n+m+1;
    for(int i=1;i<=n;i++)Insert(s,i,1),Insert(i,s,0);
    for(int i=1;i<=m;i++)Insert(n+i,t,1),Insert(t,n+i,0);
    while(bfs()){
        for(int i=0;i<=t;i++)th[i]=head[i];
        ans+=flowing(s,INF);
    }
    printf("%d",ans);return 0;
}
最大流

 

2.最小点覆盖数

选取最少的点,使任意一条边至少有一个端点被选择

有定理在,判断出一个题可以用最小点覆盖数求的时候,就直接用求最大匹配数的代码搞

poj3041Asteroids

跟上一个题按同一个套路来

题意:给出一个n*n的矩阵和矩阵上m个点,问你最少删除了多少行或列之后,点能全部消失。(联想:给出一张图上的m条边的n个相交顶点(xi, yi),问最少用其中的几个点,就可以和所有的边相关联)

思路:匈牙利算法的最小覆盖问题:最小覆盖要求在一个二分图上用最少的点(x 或 y 集合的都行),让每条连接两个点集的边都至少和其中一个点关联。根据konig定理:二分图的最小顶点覆盖数等于最大匹配数。理解到这里,将(x,y)这一点,转化为x_y的一条边,把x = a的这一边,转化为(a)这一点,剩下的就是基础的匈牙利算法实现了。
描述
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
#define maxn 501
#define maxm 10010
int n,k,num,head[maxm],link[maxn],vis[maxn];
struct node{
    int to,pre;
}e[maxm];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
int dfs(int x){
    for(int i=head[x];i;i=e[i].pre){
        int v=e[i].to;
        if(vis[v]==0){
            vis[v]=1;
            if(link[v]==0||dfs(link[v])){
                link[v]=x;return 1;
            }
        }
    }
    return 0;
}
int main(){
    scanf("%d%d",&n,&k);int x,y;
    for(int i=1;i<=k;i++){
        scanf("%d%d",&x,&y);
        Insert(x,y);
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }
    printf("%d",ans);
}
边表 AC
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 1010
using namespace std;
int n,m,e,link[maxn],re[maxn][maxn],vis[maxn],ans;
int dfs(int x){
    for(int i=1;i<=m;i++)
        if(vis[i]==0&&re[x][i]){
            vis[i]=1;
            if(link[i]==0||dfs(link[i])){
                link[i]=x;return 1;
            }
        }
    return 0;
}
int main(){
    scanf("%d%d",&n,&e);m=n;
    int x,y;
    for(int i=1;i<=e;i++){
        scanf("%d%d",&x,&y);
        re[x][y]=1;
    }
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i))ans++;
    }
    printf("%d",ans);
}
邻接矩阵 AC

3.最大独立数

选取最多的点,使任意所选两点均不相连

poj 1466 Girls and Boys

二分图的最大独立集
因为没有给出具体的男生和女生,所以可以将数据扩大一倍,即n个男生,n个女生,
根据定理,最大独立集=总数-匹配数(本题应该除以2)
给出一系列男女配对意愿信息。求一个集合中的最大人数,满足这个集合中两两的人不能配对。
Sample Input

7
0: (3) 4 5 6
1: (2) 4 6
2: (0)
3: (0)
4: (2) 0 1
5: (1) 0
6: (2) 0 1
3
0: (2) 1 2
1: (1) 0
2: (1) 0
Sample Output

5
2
题目描述
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 510
using namespace std;
int link[maxn],vis[maxn],map[maxn][maxn],n;
int dfs(int x){
    for(int i=1;i<=n;i++){
        if(vis[i]==0&&map[x][i]){
            vis[i]=1;
            if(link[i]==0||dfs(link[i])){
                link[i]=x;
                return 1;
            }
        }
    }return 0;
}
int main(){
    freopen("1.txt","r",stdin);
    while(scanf("%d",&n)!=EOF){
        memset(map,0,sizeof(map));
        memset(link,0,sizeof(link));
        for(int i=1;i<=n;i++){
            int u,w,v;
            scanf("%d: (%d)",&u,&w);u++;
            for(int j=1;j<=w;j++){
                scanf("%d",&v);v++;
                map[u][v]=map[v][u]=1;
            }
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))ans++;
        }
        printf("%d\n",n-ans/2);
    }
}
AC

4.最小路径覆盖数

对于一个 DAG(有向无环图),选取最少条路径,使得每个顶点属于且仅属于一条路径。路径长可以为 0(即单个点)。

hdu 4160 Dolls

题意:
 
n个箱子
 
下面n行 a b c 表示箱子的长宽高
 
箱子可以嵌套,里面的箱子三维都要小于外面的箱子
 
问: 露在外头的箱子有几个
 
 
 
思路:
 
只要成功匹配一条边,就等价于成功嵌套一个箱子,就是匹配一条边,露在外面的箱子就少一个
 
结果就是 n - 最大匹配数
 
 
 
注意一个条件: 箱子不可旋转,即 长对应长, 宽对应宽
 
然后就是一个裸的二分匹配
题目 思路
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 1010
#define maxm 250010
int n,head[maxn],num,one[maxn],two[maxn],three[maxn],link[maxn];
bool vis[maxn];
struct node{
    int pre,to;
}e[maxm];
void Insert(int from,int to){
    e[++num].to=to;
    e[num].pre=head[from];
    head[from]=num;
}
int dfs(int x){
    for(int i=head[x];i;i=e[i].pre){
        int v=e[i].to;
        if(vis[v]==0){
            vis[v]=1;
            if(link[v]==0||dfs(link[v])){
                link[v]=x;return 1;
            }
        }
    }
    return 0;
}
int main(){
    while(~scanf("%d",&n),n){
        if(n==0)return 0;
        memset(link,0,sizeof(link));
        memset(e,0,sizeof(e));
        memset(head,0,sizeof(head));
        int sum=0;num=0;
        for(int i=1;i<=n;i++)scanf("%d%d%d",&one[i],&two[i],&three[i]);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(one[i]<one[j]&&two[i]<two[j]&&three[i]<three[j])
                    Insert(i,j+n);
        for(int i=1;i<=n;i++){
            memset(vis,0,sizeof(vis));
            if(dfs(i))sum++;
        }
        printf("%d\n",n-sum);
    }
}
AC代码

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:BZOJ 4818 SDOI2017 序列计数

下一篇:读书笔记 effective c++ Item 45 使用成员函数模板来接受“所有