洛谷：P3386

题目背景

二分图

题目描述

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

输入输出格式

输入格式：

第一行，n,m,e

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

输出格式：

共一行，二分图最大匹配

输入输出样例

输入样例#1：

1 1 1
1 1

输出样例#1：

1

邻接矩阵（老码风）

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
using namespace std;

const int maxn(1005);
int ans;
int n,m,e;
bool vis[maxn][maxn];
bool use[maxn];
int matched[maxn];

inline bool dfs(int);

int main(){
    scanf("%d%d%d",&n,&m,&e);
    for(int i=1;i<=e;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        vis[x][y]=true;
    }
    for(int i=1;i<=n;++i){
        memset(use,false,sizeof use);
        if(dfs(i)) ans++;
    } 
    printf("%d\n",ans);
    return 0;
} 

inline bool dfs(int x){
    for(int i=1;i<=m;++i){
        if(vis[x][i]&&!use[i]){
            use[i]=true;
            if(!matched[i]||dfs(matched[i])){
                matched[i]=x;
                return true;
            }
        }
    }
    return false;
}

邻接矩阵（新码风）

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXM = 1e8;
const int MAXN = 1005;

struct node {
	int to,next;
};

node e[MAXM];

bool used[MAXN];
int head[MAXN],cnt,n,m,ee,Ans,Matched[MAXN];

void add(int from,int to) {
	e[++cnt].next = head[from];
	e[cnt].to = to;
	head[from] = cnt;
}

inline bool dfs(int u) {
	for(int i = head[u];i;i = e[i].next) {
		int v = e[i].to;
		if(!used[v]) {
			used[v] = true;
			if(!Matched[v] || dfs(Matched[v])) {
				Matched[v] = u;
				return true;
			}
		}
	}
	return false;
}

int main() {
	cin >> n >> m >> ee;
	for(int i = 1;i <= ee;++i) {
		int from,to;
		cin >> from >> to;
		if(from > n or to > m) continue;
		add(from,to);
	}
	for(int i = 1;i <= n;++i) {
		memset(used,false,sizeof used);
		if(dfs(i)) Ans++;
	}
	cout << Ans << endl;
	return 0;
}