为什么 9 分?
查看原帖
为什么 9 分?
816792
coritom楼主2025/1/12 13:54

匈牙利算法,只有 99 分,TLE 88 个点,WA 22 个点,AC 11 个点。

#include <bits/stdc++.h>
#define mid (int)((lt + rt) >> 1)
#define Max(a, b, c) max(a, max(b, c))
#define Min(a, b, c) min(a, min(b, c))
#define int long long
using namespace std;
const int N = 505;
int n, m, head[N], cnt, match[N];
bool vis[N];
struct node{
	int to, nxt;
}edge[N];
void add(int s, int e){                        //链式前向星连边 
	cnt++; 
	edge[cnt].to = e;
	edge[cnt].nxt = head[s];
	head[s] = cnt;
}
bool hungary(int x, int id){                   //匈牙利算法 
	for(int i = head[x]; i; i = edge[x].nxt){
		int y = edge[i].to;
		if(vis[y] < id){                       //y没有访问 
			vis[y] = id;
			if(!match[y] || hungary(y, id)){   //如果y没有匹配  或  y的匹配点match[y]能找到一个新的匹配 
				match[y] = x;                  //将右部的y的配对点设为左部的x 
				return 1;
			}
		}
	}
	return 0;                                  //注:只有所有点都不符合要求才行(一票同意)  
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	int a, b;
	while(1){
		cin >> a >> b;
		if(a == -1 && b == -1) break;
		add(a, b);
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){              //枚举集合中的一个点
		if(hungary(i, i)) ans++;              //找到一条增广路
	}
	cout << ans << "\n";
	if(ans == 0) return 0;
	for(int i = n + 1; i <= m; i++){
		if(match[i]) cout << match[i] << " " << i << "\n";
	}
	return 0;
}

请各大佬帮忙看看哪里有问题!

2025/1/12 13:54
加载中...