匈牙利算法,只有 9 分,TLE 8 个点,WA 2 个点,AC 1 个点。
#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;
}
请各大佬帮忙看看哪里有问题!