LGP6113/UOJ#79 「一般图最大匹配」的随机匹配AC做法

· · 题解

upd: 改了一些小错误.

本来想着随便写一发，90 就 90 咱也不带怂的 。

然后就…过掉了…

顺便也过掉了 uoj 的 52 组数据和 43+ 组的 Extra Task 。

考虑随机匹配。发现匹配本质上就是在找增广路，因为如果一个匹配 \mathbf{M} 是图 \mathbf{G} 的最大匹配的充要条件就是 \mathbf{G} 中不存在增广路。

考虑直接枚举每个点找增广路会有什么问题。对于一张二分图，一条增广路要么是一条奇链、要么是一条奇链套一个偶环，偶环上总可以完备匹配，所以绕偶数步走到原点并不改变下一条边的匹配状态。但是奇环则未必，如果经过一个奇环，就必然会存在冲突的情况。

所以随机匹配的思想就是，不找环，只找长度为奇数的简单路。这样做相当于强制断环为链，正确性难以保证。但是考虑如果多做几次，错误率就会大大下降。于是考虑多做几次这样的匹配。注意到这样做很容易被卡掉，只需要多几个奇环顺便构造一下加边顺序就可以了。所以就可以每次走的时候将边表随一下即可。

然后…用 rand() 很容易被卡掉，因为值域很小，而边数比 32768 大得多。所以用 mt19937 就可以了。

值得一提的是，以下代码为了保证正确，卡了时，大概是卡了 0.85s 左右。但是十分有趣的是…洛谷的数据在 0.0005s=0.5ms 的卡时范围之内都能过掉…这…咱也不知道该说什么好。

upd: 随机匹配似乎是无敌了。在 uoj 试了一发卡时 0.005s=5ms 的情况，依旧无压力过掉了所有 hack 数据。这个故事告诉我们：题是众生一般题，水是天下一样水。


int ans ;
int n, m ;
int vis[N] ;
int match[N] ;

clock_t st ;

mt19937 g_f ;

il db now_time(){
    return (double)(clock() - st) / CLOCKS_PER_SEC ;
}
int do_match(int x, mt19937 g_f){
    cout << x << ' ' ;
    shuffle(E[x].begin(), E[x].end(), g_f) ; vis[x] = 1 ;
    for (auto y : E[x])
        if (!match[y])
            return vis[y] = 1, match[y] = x, match[x] = y, 1 ;
    for (auto y : E[x]){
        int z = match[y] ;
        if (vis[z]) continue ;
        match[x] = y, match[y] = x, match[z] = 0 ;
        if (do_match(z, g_f)) return 1 ;
        match[y] = z, match[z] = y, match[x] = 0 ;
    }
    return 0 ;
}
int main(){
    random_device seed ;
    mt19937 g_f(seed()) ;
    cin >> n >> m ; int x, y, z ;
    for (int i = 1 ; i <= m ; ++ i)
        x = qr(), y = qr(), add_e(x, y) ; st = clock() ;
    while (now_time() < 0.85){
        for (int i = 1 ; i <= n ; ++ i)
            if (!match[i])
                fill(vis + 1, vis + n + 1, 0), ans += do_match(i, g_f), puts("") ;
    }
    cout << ans << '\n' ;
    return debug(match, 1, n), 0 ;
}