欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P3386[模板]二分图匹配

程序员文章站 2024-03-17 15:08:40
...

题目背景

二分图

感谢@一扶苏一 提供的hack数据

题目描述

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

输入输出格式

输入格式:

 

第一行,n,m,e

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

 

输出格式:

 

共一行,二分图最大匹配

 

输入输出样例

输入样例#1: 

1 1 1
1 1

输出样例#1: 

1

其实我只是来存个档的

匈牙利算法

1.邻接矩阵

#include<iostream>
#include<stdio.h>
using namespace std ;
int e[1010][1010] ;
int EE;
int match[1010] ;
int book[1010] ;
int n , m ;
int dfs(int u){//匈牙利算法
    for(int i = 1 ; i <= m ; i ++){
        if(book[i] == 0 && e[u][i] == 1){
            book[i] = 1 ;
            if(match[i] == 0 || dfs(match[i])){
                match[i] = u ;
                return 1 ;
            }
        }
    } 
    return 0 ;
} 
int t1 , t2 , sum ;
int main(){
    cin >> n >> m >> EE ;  
    while(EE --){
        cin >> t1 >> t2 ; 
        e[t1][t2] = 1 ;
    }
    for(int i = 1 ; i <= n ; i ++) match[i] = 0 ;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= n ; j ++) book[j] = 0 ;
        if(dfs(i)) sum ++ ;
    }
    cout << sum ;
    return 0 ;
}

2.邻接表

 

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 1010000 
using namespace std ;
int match[maxn] ;
struct dy{
    int x , y , z , next ;
}a[maxn] ;
bool book[maxn] ;int t ;
int n , m , k ;
int head[maxn] , vis[maxn] ;
void add(int u , int v){
    a[++t].x = u ;
    a[t].y = v ;
    a[t].z = 1 ;
    a[t].next = head[u] ;
    head[u] = t ;
}
bool dfs(int u){
    for(int i = head[u] ; i ; i = a[i].next){
    	int v = a[i].y ;
        if(!book[v]){
            book[v] = 1 ;
            if(!match[v] || dfs(match[v])){
                match[v] = u ;
                return 1 ;
            }
        }
    }
    return 0 ;
}
int main(){
    scanf("%d%d%d",&n,&m,&k) ;
    while(k --){
        int u , v ;
        scanf("%d%d",&u,&v) ;
        if(u > n || v > m) continue ;
        add(u,v) ;
    }int sum = 0;
    for(int i = 1 ; i <= n ; i ++){
        for(int j = 1 ; j <= n ; j ++) book[j] = 0 ;
        if(dfs(i)) sum ++ ;
    }
    printf("%d\n",sum) ;
    return 0 ;
}

return 0 ; 

 

相关标签: 二分图