匈牙利算法 MLE 30pts求调
查看原帖
匈牙利算法 MLE 30pts求调
999274
CNS_5t0_0r2楼主2024/8/1 14:04
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9,M = 1e4 + 9;
int n,tim;
struct edge{
	int to,nex;
} e[(N + M) << 1];
int head[N + M],ecnt;
void addedge(int u,int v){
	ecnt++;
	e[ecnt] = (edge){v,head[u]};
	head[u] = ecnt;
}
int vis[N + M];
int match[N + M];
bool dfs(int u){
    vis[u] = tim;
	for(int i = head[u];i;i = e[i].nex){
		int v = e[i].to;
		if(vis[v] == tim)
			continue;
		if(!match[v] || dfs(match[v])){
			match[v] = u;
			return true;
		}
	}
	return false;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n;
	for(int i = 1;i <= n;i++){
		int u,v;
		cin >> u >> v;
		addedge(u,i + 10000);
		addedge(v,i + 10000);
	}
	for(int i = 1;i <= 10001;i++){
	    tim = i;
		if(!dfs(i)){
		    cout << i - 1;
		    return 0;
		}
	}
	return 0;
}
2024/8/1 14:04
加载中...