洛谷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 ;
上一篇: 二分图判断(染色法)