刚学 OI 的萌新来看自己的代码的一点疑问捏 qwq
查看原帖
刚学 OI 的萌新来看自己的代码的一点疑问捏 qwq
298549
SIXIANG32楼主2022/10/3 20:38
//SIXIANG
#include <iostream>
#include <cstring>
#include <vector> 
#define MAXN 200000
#define QWQ cout << "QWQ" << endl;
using namespace std;
vector <int> gra[MAXN + 10];
bool vis[MAXN + 10];
int match[MAXN + 10];
bool dfs(int u) {
	for(int p = 0; p < gra[u].size(); p++) {
		int v = gra[u][p];
		if(vis[v]) continue;
		vis[v] = 1;
		if(!match[v] || dfs(match[v])) {
			match[v] = u;
			return 1;
		}
	}
	return 0;
}
int main() {
	int n, m, e; cin >> n >> m >> e;
	for(int p = 1, x, y; p <= e; p++) {
		cin >> x >> y;
		gra[x].push_back(y);
	}
	int ans = 0;
	for(int p = 1; p <= n; p++) {
		memset(vis, 0, sizeof(vis));
		if(dfs(p)) ans++;
	}
	cout << ans << endl;
}

(其实类似于我最早的代码改了个码风捏 qwq)

不是很理解为什么要建立单向边诶,二分图不应该是无向图吗?还有为什么这里的右部图的编号不是 i+n 啊,我自己不是很理解,求巨佬指教/kel/kel/kel

2022/10/3 20:38
加载中...