科技:一般图最大匹配的另类做法

其实这个做法也不是我自己发明的，是在北京集训的时候由广州二中的神犇sukai提出的。
看现在也不是很多人知道的样子，所以拿来普及一发。

关于一般图的最大匹配，正常人肯定会写带花树。然而这个东西是目前最复杂的确定性算法之一。
如果我懒得(不会)写带花树，怎么破呢？
当时sukai面对一个只有一个点的图，要求最大匹配。于是他想到了，大力增广。
是的，如果我们在这张图上大力dfs寻找增广路的话，是不是就可做了呢？
显然单次增广是存在反例的。但是如果我们多次增广，且每次random_shuffle一下出边，是不是就没那么容易卡了。
实际上，当增广次数达到n，这个东西的正确性是可证明的(反正sukai说他手玩6个点的图全都正确)。
然而一般情况下增广10~20次就能够基本保证正确。
于是这个黑科技就出现了QAQ。

代码(UOJ79):

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 const int maxn=5e2+1e1;
 8 
 9 vector<int> in[maxn];
10 int fa[maxn];
11 bool vis[maxn],used[maxn];
12 
13 inline bool dfs(int pos) {
14     vis[pos] = 1 , random_shuffle(in[pos].begin(),in[pos].end());
15     for(unsigned i=0;i<in[pos].size();i++)
16         if( !used[in[pos][i]] ) {
17             used[pos] = used[in[pos][i]] = 1 ,
18             fa[pos] = in[pos][i] , fa[in[pos][i]] = pos;
19             return 1;
20         }
21     for(unsigned i=0;i<in[pos].size();i++) {
22         const int tar = in[pos][i] , mth = fa[tar];
23         if( vis[mth] ) continue;
24         used[pos] = 1 , fa[tar] = pos , fa[pos] = tar , used[mth] = fa[mth] = 0;
25         if( dfs(mth) ) return 1;
26         used[mth] = 1 , fa[tar] = mth , fa[mth] = tar , used[pos] = fa[pos] = 0;
27     }
28     return 0;
29 }
30 
31 int main() {
32     static int n,m,ans;
33     scanf("%d%d",&n,&m);
34     for(int i=1,a,b;i<=m;i++) scanf("%d%d",&a,&b) , in[a].push_back(b) , in[b].push_back(a);
35     for(int T=1;T<=10;T++) for(int i=1;i<=n;i++) if( !used[i] ) memset(vis,0,sizeof(vis)) , dfs(i);
36     for(int i=1;i<=n;i++) ans += used[i];
37     printf("%d\n",ans>>1);
38     for(int i=1;i<=n;i++) printf("%d%c",fa[i],i!=n?' ':'\n');
39     return 0;
40 }

View Code

提交记录为:
http://uoj.ac/submission/242287
欢迎神犇前来来hack!

科技:一般图最大匹配的另类做法

推荐阅读