《一般图最大匹配》学习总结
带花树学不会，不玩了。咕掉。
随机化
来学随机化吧。。。
实际上在随机数据上表现甚至优于带花树，不过他为什么要随机而且为什么随机就能搞我也不知道。
就背一个板子就好了。
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=1e3+10;
int n,m,mt[MAXN];
bool vis[MAXN];
vector<int> e[MAXN];
mt19937 rnd(time(0));
int dfs(int x) {
shuffle(e[x].begin(),e[x].end(),rnd);
vis[x]=1;
for(auto t:e[x]) {
if(!mt[t]) {
vis[t]=1; mt[t]=x; mt[x]=t;
return true;
}
}
for(auto t:e[x]) {
int tt=mt[t];
if(vis[tt]) continue;
mt[x]=t; mt[t]=x; mt[tt]=0;
if(dfs(tt)) return true;
mt[t]=tt; mt[tt]=t; mt[x]=0;
}
return false;
}
int main () {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) {
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
double start=clock();
int ans=0;
while((double)(clock()-start)/CLOCKS_PER_SEC<=0.80) {
for(int i=1;i<=n;++i) {
if(!mt[i]) {
memset(vis,0,sizeof(vis));
ans+=dfs(i);
}
}
}
printf("%d\n",ans);
for(int i=1;i<=n;++i) printf("%d ",mt[i]);
return 0;
}
P6113 【模板】一般图最大匹配
模板题
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=1e3+10;
int n,m,mt[MAXN];
bool vis[MAXN];
vector<int> e[MAXN];
mt19937 rnd(time(0));
int dfs(int x) {
shuffle(e[x].begin(),e[x].end(),rnd);
vis[x]=1;
for(auto t:e[x]) {
if(!mt[t]) {
vis[t]=1; mt[t]=x; mt[x]=t;
return true;
}
}
for(auto t:e[x]) {
int tt=mt[t];
if(vis[tt]) continue;
mt[x]=t; mt[t]=x; mt[tt]=0;
if(dfs(tt)) return true;
mt[t]=tt; mt[tt]=t; mt[x]=0;
}
return false;
}
int main () {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) {
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
double start=clock();
int ans=0;
while((double)(clock()-start)/CLOCKS_PER_SEC<=0.80) {
for(int i=1;i<=n;++i) {
if(!mt[i]) {
memset(vis,0,sizeof(vis));
ans+=dfs(i);
}
}
}
printf("%d\n",ans);
for(int i=1;i<=n;++i) printf("%d ",mt[i]);
return 0;
}
P4258 [WC2016] 挑战NPC
又是一道人类智慧建模题。
首先直接建肯定是不行。
我们将一个筐拆成 \(3\) 个点。然后三个点之间两两连边，由于题目保证了一定有完美匹配，我们讨论一下筐内小球数量的情况，对于贡献情况：
-
筐内有没有小球，没有贡献。
-
筐内有一个小球，贡献为 \(2\) ，这时候多了 \(1\) 的贡献，因为相当于自己是一个没有满半的桶。
-
筐内有两个小球，贡献为 \(2\) ，这时候自己没有满半，实际贡献为 \(0\) ，所以要减去 \(2\) 的贡献。
-
筐内有三个小球，要减 \(3\)
这时候我们就可以发现，筐内有多少个小球就要减去多少的贡献。
这样建出模来跑就行了。
点击查看代码
#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int MAXN=4010;
int T;
int n,m,E;
int mt[MAXN],vis[MAXN];
vector<int> e[MAXN];
int id(int opt,int x) {
return n+opt*m+x;
}
void add(int f,int t) {
e[f].push_back(t);
e[t].push_back(f);
}
mt19937 rnd(time(0));
bool dfs(int x) {
shuffle(e[x].begin(),e[x].end(),rnd);
vis[x]=1;
for(auto t:e[x]) {
if(!mt[t]) {
vis[t]=1; mt[x]=t; mt[t]=x;
return true;
}
}
for(auto t:e[x]) {
int tt=mt[t];
if(vis[tt]) continue;
mt[x]=t; mt[t]=x; mt[tt]=0;
if(dfs(tt)) return true;
mt[x]=0; mt[t]=tt; mt[tt]=t;
}
return false;
}
int main () {
scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&n,&m,&E);
for(int i=1;i<=E;++i) {
int x,y;
scanf("%d%d",&x,&y);
add(x,id(0,y));
add(x,id(1,y));
add(x,id(2,y));
}
for(int i=1;i<=m;++i) {
add(id(0,i),id(1,i));
add(id(0,i),id(2,i));
add(id(1,i),id(2,i));
}
double start=clock();
int ans=0;
memset(mt,0,sizeof(mt));
while(double(clock()-start)/CLOCKS_PER_SEC<=0.15) {
for(int i=1;i<=n+3*m;++i) {
if(!mt[i]) {
memset(vis,0,sizeof(vis));
ans+=dfs(i);
}
}
}
printf("%d\n",ans-n);
for(int i=1;i<=n;++i) {
printf("%d ",(mt[i]-n-1)%m+1);
}
puts("");
for(int i=1;i<=n+3*m;++i) {
e[i].clear();
}
}
return 0;
}