[学习笔记] 邓老师调整法

本篇博客和邓老师论文的区别就是不严谨有代码。

简介

组合优化问题有如下形式：一个问题有一些合法解和不合法解，每个合法解有一个对应的权值，你需要在所有合法解中找出权值最大的一个。

一种显然的做法是：先任取一个合法解，然后对合法解进行微调使得权值变大，一直操作直到无法进行。这一算法看似简单，但在许多问题中有出色的表现。

值得注意的是，这种调整方法得到的答案是不降的，它并不像模拟退火一样有一定概率接受劣解，所以调整方式不能让当前解被局限（能通过答案不降的路径调整到最优解\(/\)较优解）

下面将结合不同的题目类型讲解邓老师调整法的应用，着重体会其思想。

一般图最大匹配

点此看题

我们考虑一个未匹配的点集 \(V\)，每次我们从中随机出一个点 \(u\)，然后考虑 \(u\) 的邻接点中是否存在未配对的。如果存在那么随机一个直接匹配，答案\(+1\)；否则我们随机一个已匹配的点 \(v\)，断开 \(v\) 和其匹配点的边，然后把 \((u,v)\) 作为新的匹配加入。

一直重复上述步骤到超时为止，很可惜的是无法通过 \(\tt extra\ test\)

#include 
#include 
#include 
#include  
#include 
using namespace std;
const int M = 505; 
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,m,k,ans,mat[M],s[M];vector g[M];
int random(int x)
{
	return (1ll*rand()*rand()+rand())%x;
}
void zxy()
{
	k=0;
	for(int i=1;i<=n;i++)
		if(!mat[i] && !g[i].empty()) s[++k]=i;
	if(!k) return ;//perfect!
	int u=s[random(k)+1];k=0;
	for(int v:g[u]) if(!mat[v])
		s[++k]=v;
	if(k)//random a match node
	{
		int v=s[random(k)+1];
		mat[u]=v;mat[v]=u;return ;
	}
	//adjust it
	for(int v:g[u]) s[++k]=v;
	int v=s[random(k)+1];
	mat[mat[v]]=0;
	mat[u]=v;mat[v]=u;
}
signed main()
{
	n=read();m=read();srand(time(0));
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	while(1.0*clock()/CLOCKS_PER_SEC<=0.95) zxy();
	for(int i=1;i<=n;i++)
		if(mat[i]) ans++;
	printf("%d\n",ans/2);
	for(int i=1;i<=n;i++)
		printf("%d ",mat[i]);
}