单点时限: 2.0 sec
内存限制: 512 MB
在某个不知名的算法课上，老师提出了这样一个问题。
现有一个没有重边的二分图。每次操作是从二分图中找到一个完美匹配并将匹配边从二分图中删除。求最多能进行多少次这样的删除操作？
编写程序解决该问题。程序读入二分图左右两边点的个数 $n$。左边的点编号为 $1$ 到 $n$，右边的点编号也为 $1$ 到 $n$；再读入二分图中的边。$(i,j)$ 表示左边的 $i$ 号点和右边的 $j$ 号点相连。
有一个（很显然是错误的）算法采用了如下的贪心策略：
这个算法如此错误 (so ridiculous) 以至于你随随便便都能举出一个反例。所以我们进行了如下改进：
使用一种随机迭代算法。在每一次迭代中，我们对右边的点的编号进行打乱，然后运行上面的（错误）算法，然后不断更新最优解。如果在 10 次迭代中内都没有找到更优的解，我们认为更优的解很有可能不存在，就返回答案。而一旦有出现更优的解，迭代剩余次数就又重新变成 10 次了。
至于打乱右边的点的编号有什么好处？打乱一下总能让我们看到一些之前看不到的东西的啊！（口胡）
其实你不妨看一下匈牙利算法的遍历顺序。
请构造一组数据使这一随机算法在至少 100 个种子下失败。评测时会使用正确的算法跑出答案进行对比。如果随机算法得出的答案与正确答案不一致，就认为失败。
下面是该解法的一个 C++ 实现。题目保证所用的判题程序和下面所展示的程序在功能和实现上是完全一致的。
#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;
}
return 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)
bp.add_edge(e.first, permutation[e.second]);
int current_ans = 0;
while (bp.hungary() == n) { // a perfect match found
current_ans++; // increase answer
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;
}
第一行输出两个整数 $n$, $m$ ($1 \le n \le 50, 1 \le m \le n^2$)。
接下来 $m$ 行每行两个整数 $u$, $v$ ($1 \le u,v \le n$)，表示左边的 $u$ 号点与右边的 $v$ 号点相连。
注意该图不能有重边，亦即有序数对 $(u,v)$ 在输出中至多出现一次。
3 4 1 1 2 2 3 2 3 3
样例只是给出了一种可能的输出（并不意味着能通过测试）。