KM算法可以解决该问题吗？？？我郁闷了许久了，至今尚未解决，高手帮忙，谢谢!!!
#include <iostream>
#include <cmath>
using namespace std;

const int MAX=110;
int n;
double colonies[MAX][2];
double apple[MAX][2];
int match[MAX];
double lx[MAX],ly[MAX];
int visx[MAX],visy[MAX];
double map[MAX][MAX];

bool Dfs(int u)   
{
	visx[u]=1;
	for (int v=1;v<=n;v++)
	{
		if (!visy[v] && lx[u]+ly[v] == map[u][v])//<1e-10)
		{
			visy[v]=1;
			if (match[v]==0 || Dfs(match[v]))
			{
				match[v]=u;
				return true;
			}
		}
	}
	return false;
}



void BestMatch()   //求最佳匹配：最小权匹配
{
	double sum=0;
	int i,j,k;
	memset(lx,127,sizeof(lx));  //将lx初始化为很大的数，不是127
        memset(ly,0,sizeof(ly));
	/* 此处lx取最小值，因为是求最小权匹配 */ 
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++) 
		{
			if (map[i][j] < lx[i])
			{
				lx[i]=map[i][j];
			}
		}
	}
	memset(match,0,sizeof(match));
	for (i=1;i<=n;i++)
	{
		while (true)
		{
			memset(visx,0,sizeof(visx));
			memset(visy,0,sizeof(visy));
			double min=10000000000;
			/* 如果找到最佳匹配，及时退出 */
			if (Dfs(i))
			{
				break;
			}
			for (k=1;k<=n;k++)
			{
				if (visx[k])
				{
					for (j=1;j<=n;j++)
					{
											                                if (!visy[j] && map[k][j]-lx[k]-ly[j]<min)
						{
							min=map[k][j]-lx[k]-ly[j];
						}
					}
				}
			}
			/* 修改顶标。 */
			for (j=1;j<=n;j++)
			{
				if (visx[j])
				{
					lx[j]+=min;
				}
				if (visy[j])
				{
					ly[j]-=min;
				}
			}
		}
	}
	for (i=1;i<=n;i++)
	{
		for (j=1;j<=n;j++)
		{
			if (match[j] == i)
			{
				cout<<j<<endl;
				break;
			}
		}
	}
}

void GetDis()
{
	
	memset(map,0,sizeof(map));
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			
			double dx=(colonies[i][0]-apple[j][0])*(colonies[i][0]-apple[j][0]);
			double dy=(colonies[i][1]-apple[j][1])*(colonies[i][1]-apple[j][1]);
		//	cout<<colonies[i][0]<<"  "<<colonies[i][1]<<"  "<<apple[i][0]<<"  "<<apple[i][1]<<endl;
		//	map[i][j]=sqrt(dx+dy); 
			map[i][j]=dx+dy;  //计算的是距离的平方
				
		}
	}
}

int main()
{
	int i,j;
	cin>>n;
	for (i=1;i<=n;i++)
	{
		cin>>colonies[i][0]>>colonies[i][1];
	}
	for (i=1;i<=n;i++)
	{
		cin>>apple[i][0]>>apple[i][1];
	}
	GetDis();
	BestMatch();  
	return 0;
}
 

• re :可怜的KM啊 (32) yongheng5871 2010-12-28 22:23:14
  • Re:re :可怜的KM啊 (54) zdf615328619 2011-12-20 17:25:19