二分图匹配模板

虽然说这玩意似乎没什么好写的.....

但是不经常用....时不时就忘了....还是记一些东西吧...

首先是Hungary算法.....邻接矩阵实现.....

bool M[205][205];
bool used[205];
int mat[205];

bool DFS(int x)
{
	for(int i=0;i<m;i++)
	if(M[x][i] && !used[i])
	{
		used[i]=true;
		if( mat[i]==-1 || DFS(mat[i]) )
		{
			mat[i]=x;
			return true;
		}
	}
	return false;
}
.....
	int res=0;
	memset(mat,0xFF,sizeof(mat));
	for(int i=0;i<n;i++)
	{
		memset(used,0,sizeof(used));
		res+=DFS(i);
	}
.....

M是边表,存储集合A到集合B的有向边.

使用used来使得对于每次搜索,集合B只访问一次.

mat[i]表示集合B中元素i,在A中对应的元素是哪个.

要点:

1.注意对应关系.我们只存储从集合A到集合B的边.used的tag打在集合B的元素上.

2.千万别忘了初始化....

3.由于算法复杂度比较高,所以一般不会吝啬地用链表邻接表.如果可匹配得边数比较少而点数比较多,就用链表邻接表.

下面是邻接表写的Hungary.没什么区别...

struct edge
{
	int in;
	edge*nxt;
}pool[50000];
edge*et=pool;
edge*eds[205];
void addedge(int i,int j)
{ et->in=j; et->nxt=eds[i]; eds[i]=et++; }
#define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)


bool used[205];
int mat[205];

bool DFS(int x)
{
	FOREACH_EDGE(i,x)
	if(!used[i->in])
	{
		used[i->in]=true;
		if( mat[i->in]==-1 || DFS(mat[i->in]) )
		{
			mat[i->in]=x;
			return true;
		}
	}
	return false;
}
.....
.....
int res=0;
memset(mat,0xFF,sizeof(mat));
for(int i=0;i<n;i++)
{
	memset(used,0,sizeof(used));
	res+=DFS(i);
}
....
....

如果是带权匹配的话.....

果断网络流!

不就是120行嘛!

顺便贴了新的文件头.....

#include <cstdio>
#include <fstream>
#include <iostream>

#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>

#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <list>

typedef unsigned int uint;
typedef long long int ll;
typedef unsigned long long int ull;
typedef double db;

#define DBG printf("*")

using namespace std;

int getint()
{
	int res=0;
	char c=getchar();
	bool mi=false;
	while( (c<'0' || c>'9') && !feof(stdin) ) mi=(c=='-'),c=getchar();
	while( ('0'<=c && c<='9') && !feof(stdin) ) res=res*10+c-'0',c=getchar();
	return mi ? -res : res;
}
ll getll()
{
	ll res=0;
	char c=getchar();
	bool mi=false;
	while( (c<'0' || c>'9') && !feof(stdin) ) mi=(c=='-'),c=getchar();
	while( ('0'<=c && c<='9') && !feof(stdin) ) res=res*10+c-'0',c=getchar();
	return mi ? -res : res;
}
void fillarray(int*k,int v,int size)
{ for(int i=0;i<size;i++) k[i]=v; }
void fillarray(ll*k,ll v,int size)
{ for(int i=0;i<size;i++) k[i]=v; }
void fillarray(char*k,char v,int size)
{ for(int i=0;i<size;i++) k[i]=v; }
void fillarray(db*k,db v,int size)
{ for(int i=0;i<size;i++) k[i]=v; }

//==============================================================================
//==============================================================================
//==============================================================================
//==============================================================================


db INF=1e20;
db eps=1e-11;
bool fequal(db a,db b)
{ return fabs(a-b)<eps; }

//maxflow

struct edge
{
	int in;
	int c;
	db v;
	edge*nxt;
	edge*ptr;
}pool[100000];
edge*et=pool;
edge*eds[1000];
void addedge(int i,int j,int c,db v)
{
	et->ptr=et+1;
	et->in=j; et->c=c; et->v=v; et->nxt=eds[i]; eds[i]=et++;
	et->ptr=et-1;
	et->in=i; et->c=0; et->v=-v; et->nxt=eds[j]; eds[j]=et++;
}
#define FOREACH_EDGE(i,j) for(edge*i=eds[j];i;i=i->nxt)

int n;
int st,ed;

db cost;
db dist[1000];
bool used[1000];
int DFS(int x,int mi)
{
	if(x==ed) return mi;
	used[x]=true;
	int res=0; int c;
	FOREACH_EDGE(i,x)
	if(i->c>0 && !used[i->in] && fequal(dist[x]+i->v,dist[i->in]) && ( c=DFS(i->in,min(i->c,mi)) ))
	{
		res+=c;
		i->c-=c;
		i->ptr->c+=c;
		mi-=c;
		cost+=db(c)*i->v;
		if(mi==0) break; 
	}
	used[x]=false;
	if(res==0) dist[x]=INF;
	return res;
}

int qh,qt;
int q[4000000];
db DINIC()
{
	db res=0.0;
	
	while(true)
	{
		fillarray(dist,INF,n);
		qh=qt=0;
		q[qt++]=st;
		dist[st]=0;
		while(qh!=qt)
		{
			int&cur=q[qh];
			FOREACH_EDGE(i,cur)
			if( i->c>0 && dist[i->in] > dist[cur] + i->v )
			{
				dist[i->in]=dist[cur]+i->v;
				q[qt++]=i->in;
			}
			qh++;
		}
		
		if(dist[ed]>=INF) break;
		
		cost=0;
		if(0==DFS(st,(1<<28)-1)) break;
		res+=cost;
	}
	
	return res;
}


//=================================================

int ptot;
int mx[1050];
int my[1050];
int ex[1050];
int ey[1050];

db dst(int i,int j)
{ return sqrt(db(mx[i]-ex[j])*db(mx[i]-ex[j])+db(my[i]-ey[j])*db(my[i]-ey[j])); }

//blocks define
#define MISSILE(i) (i)
#define ENEMY(i) ((i)+ptot)

int main()
{
	ptot=getint();
	for(int i=0;i<ptot;i++)
	mx[i]=getint(),my[i]=getint();
	for(int i=0;i<ptot;i++)
	ex[i]=getint(),ey[i]=getint();
	
	st=ptot*2;
	ed=st+1;
	n=ed+1;
	
	for(int i=0;i<ptot;i++)
	for(int j=0;j<ptot;j++)
	addedge(MISSILE(i),ENEMY(j),1,dst(i,j));
	
	for(int i=0;i<ptot;i++)
	addedge(st,MISSILE(i),1,0.0);
	
	for(int i=0;i<ptot;i++)
	addedge(ENEMY(i),ed,1,0.0);
	
	printf("%.3lf\n",DINIC());
	
	return 0;
}