如题,两份代码,不知道有什么区别
邻接矩阵(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;
}
玄关求助,谢谢