二分图最大匹配为什么一用链式前向星就废?
  • 板块灌水区
  • 楼主_cheng
  • 当前回复16
  • 已保存回复16
  • 发布时间2024/9/7 10:59
  • 上次更新2024/9/7 14:16:07
查看原帖
二分图最大匹配为什么一用链式前向星就废?
835255
_cheng楼主2024/9/7 10:59

如题,两份代码,不知道有什么区别

邻接矩阵(AC)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 505, M = 505;

int n, m, e;
int bl[M] = {};
bool vis[M] = {};
bool edge[N][M]=  {};

bool match(int x){
	for(int p=1; p<=m; p++){
		if((!edge[x][p]) || vis[p])  continue ;
		vis[p] = 1;
		if(bl[p]==0)            return bl[p] = x, 1;
		else if(match(bl[p]))   return bl[p] = x, 1;
	}
	return 0;
}

int main(){
	std:: scanf("%d%d%d", &n, &m, &e);
	for(int i=1; i<=e; ++i){
		int u, v;  std:: scanf("%d%d", &u, &v);
		edge[u][v] = 1;
	}
	
	int cnt = 0;
	for(int i=1; i<=n; ++i){
		for(int j=1; j<=m; ++j)  vis[j] = 0;
		if(match(i))  ++ cnt;
	}  
	std:: printf("%d", cnt);
	return 0;
}

链式前向星(WA)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
using ll = long long int;
const int N = 5005, M = 5005, E = 500005;

int n, m, e;
bool has[N][N] = {};

struct Graph{
	struct edge{int to, nxt;}  e[E*2] = {};
	int cnte = 0;
	int head[N + M] = {};
	inline void add(int u, int v)  {e[++cnte] = {v, head[u]}, head[u] = cnte;}
}; Graph g;

bool belong[M+N] = {};  
bool vis[M+N] = {};

bool match(Graph &g, int x){        //匈牙利求最大匹配
	for(int i=g.head[x]; i; i=g.e[i].nxt){
		if(vis[g.e[i].to])  continue ;
		vis[g.e[i].to] = 1;
		if(belong[g.e[i].to] == 0){    //没主人, 直接拿 
			return belong[g.e[i].to] = x, 1;
		}else{       //有主人, 抢掉
			if(match(g, belong[g.e[i].to]))  return belong[g.e[i].to] = x, 1;
		} 
	}
	return 0;
}

int main(){
	std:: scanf("%d%d%d", &n, &m, &e);
	for(int i=1; i<=e; ++i){
		int u, v;  std:: scanf("%d%d", &u, &v);
		if(!has[u][v])   g.add(u, N+v), has[u][v] = 1;
	}
	
	int cnt = 0;
	for(int i=1; i<=n; ++i){
		memset(vis, 0, sizeof vis);
		if(match(g, i))  ++ cnt;
	}  
	std:: printf("%d", cnt);
	return 0;
}

玄关求助,谢谢

2024/9/7 10:59
加载中...