# 3566. 我绝不会 WA

1. 使用匈牙利算法 (Hungarian algorithm) 找一个完美匹配。如果失败，返回答案。否则，答案加 1。
2. 删去这个完美匹配中的匹配边。回到第 1 步。

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
const int maxn = 300;

struct Bipartite {
// This is just a simple hungarian algorithm.
int from[maxn], use[maxn], mat[maxn][maxn], n, tot;

bool match(int x) {
for (int v = 1; v <= n; ++v)
if (mat[x][v] && !use[v]) {
use[v] = 1;
if (from[v] == -1 || match(from[v])) {
from[v] = x;
return 1;
}
}
return 0;
}

void delete_match() {
for (int i = 1; i <= n; ++i)
mat[from[i]][i] = 0;
}

int hungary() {
tot = 0;
memset(from, -1, sizeof from);
for (int i = 1; i <= n; ++i) {
memset(use, 0, sizeof use);
if (match(i)) ++tot;
}
}

void init(int n) {
memset(mat, 0, sizeof mat);
this->n = n;
}

void add_edge(int u, int v) {
mat[u][v] = 1;
}
} bp;

int solve_bipartite_annealing(int n, vector<P> edges) {
// Example: solve_bipartite_annealing(3, {{1, 1}, {2, 2}, {3, 2}, {3, 3}});
int temperature = 10, best = 0;
int permutation[maxn];
iota(permutation + 1, permutation + n + 1, 1); // permutation = [1, 2, 3, ...]

while (temperature > 0) {
temperature--;
bp.init(n);
random_shuffle(permutation + 1, permutation + n + 1);
// permutation[1..n] is a random permutation of 1..n

for (P &e: edges)
int current_ans = 0;
while (bp.hungary() == n) {  // a perfect match found
bp.delete_match();  // delete matching edges
}
if (current_ans > best) {  // a better solution found
best = current_ans;
temperature = 10;  // nice, we are motivated!
}
}
return best;
}


### 样例

Input

Output
3 4
1 1
2 2
3 2
3 3


### 提示

17 人解决，56 人已尝试。

18 份提交通过，共有 181 份提交。

7.2 EMB 奖励。