匈牙利算法

#include <bits/stdc++.h>
using namespace std;
const int N = 1005, M = 105;
int n, m, tot;
double c[N];
int matx[N], maty[N], id[N * M];
bool vis[N], g[M][N];
inline bool dfs(int u) {//匈牙利算法
for(int i = 1; i <= tot; i++) {
if(!g[u][id[i]] || vis[i]) continue;
vis[i] = 1;
if(!maty[i] || dfs(maty[i])) {
matx[u] = i;
maty[i] = u;
return 1;
}
}
return 0;
}
int main() {
cin >> n >> m;
for(int i = 1, x; i <= m; i++) {
cin >> x;
for(int j = 1, y; j <= x; j++) {
cin >> y;
c[y] += 1.0 / x;
g[i][y] = 1;
}
}
for(int i = 1; i <= n; i++) {
int f = ceil(c[i]);
while(f--) id[tot] = i;//将 i 拆成 f 个点
}
for(int i = 1; i <= m; i) {
memset(vis, 0, sizeof vis);
if(!dfs(i)) {
cout << -1 << '\n';
return 0;
}
}
for(int i = 1; i <= m; i++)
cout << id[matx[i]] << '\n';
return 0;
}