2400.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include"iostream.h"
#include"string.h"
#include"stdio.h"


#define valuetype int

#define null 0
const int size=20;


bool maxmatch(int n,int m,bool w[size][size],int *p,bool *setn,bool *setm)
{
	int p_n[size];
	int p_m[size];
	bool sign[size];
	int q[size],from[size],s,t;

	int i,j,link,now,h;
	

	for(i=0;i<n;i++)p_n[i]=-1;
	for(j=0;j<m;j++)p_m[j]=-1;

	for(i=0;i<n;i++)
	if(p_n[i]==-1)
	{
		for(j=0;j<m;j++)sign[j]=0;
				
		s=1;link=-1;

		from[0]=-1;
		q[0]=size-1;
		p_m[size-1]=i;
		
		for(t=0;t<s;t++)
		{
			now=q[t];
			for(j=0;j<m;j++)
			{
				if(w[p_m[now]][j]!=null&&sign[j]==0)
				{
					sign[j]=1;
					q[s]=j;
					from[s++]=t;
					
					if(p_m[j]==-1)
					{
						link=s-1;
						break;
					}
				}
			}
			
			if(j<m)break;
		}

		if(t<s)
		{
			while(from[link]!=-1)
			{
				h=from[link];
				p_m[q[link]]=p_m[q[h]];
				
				p_n[p_m[q[h]]]=q[link];
				link=h;
			}

		}
		else
		{
			for(j=0;j<n;j++)setn[j]=0;
			
			for(j=0;j<m;j++)setm[j]=0;

			for(j=0;j<s;j++)
			{
				setn[p_m[q[j]]]=1;
				if(j)setm[q[j]]=1;
			}
	
			return 0;
		}
	}


	for(i=0;i<n;i++)
	{
		if(p)p[i]=p_n[i];
		
	}
	
	return 1;
}


valuetype maxvaluematch(int l,valuetype w[][size])
{
	valuetype x[size],y[size],af;
	bool edge[size][size],setn[size],setm[size];
	int i,j,p[size];
	
	for(i=0;i<l;i++)y[i]=0;

	for(i=0;i<l;i++)
	{
		x[i]=0;
		for(j=0;j<l;j++)
			if(w[i][j]>x[i])x[i]=w[i][j];
	}

	do
	{	
		for(i=0;i<l;i++)
		for(j=0;j<l;j++)
			if(w[i][j]==x[i]+y[j])edge[i][j]=1;
			else edge[i][j]=0;

		if(maxmatch(l,l,edge,p,setn,setm))
		{
			valuetype answer=0;
			for(i=0;i<l;i++)
				answer+=w[i][p[i]];
			
			return answer;
		}
		
		af=0;
		for(i=0;i<l;i++)
		{
			if(setn[i])
				for(j=0;j<l;j++)
					if(!setm[j])
					{
						if(af==0||x[i]+y[j]-w[i][j]<af)af=x[i]+y[j]-w[i][j];
					}
		}

		for(i=0;i<l;i++)if(setn[i])x[i]-=af;

		for(j=0;j<l;j++)if(setm[j])y[j]+=af;
	}while(1);

	return 0;
}

//////////////////////////////////////////////////////////////


int v;
int e[20][20],n,cas;
int p[20];

void del_copy(int a[20][20],int b[20][20],int c,int d,int sn)
{
	int i,j;
	
	for(i=0;i<c;i++)
	{
		for(j=0;j<d;j++)
			a[i][j]=b[i][j];
		for(j=d+1;j<sn;j++)
			a[i][j-1]=b[i][j];
	}
	
	for(i=c+1;i<sn;i++)
	{
		for(j=0;j<d;j++)
			a[i-1][j]=b[i][j];
		for(j=d+1;j<sn;j++)
			a[i-1][j-1]=b[i][j];
	}
}

void print()
{
	int sign[20],i,j,k;
	cas++;
	printf("Best Pairing %d\n",cas);
	
	
	for(i=0;i<n;i++)
		sign[i]=1;
	
	for(i=0;i<n;i++)
	{
		for(j=0,k=0;j<n;j++)
		{
			if(sign[j])k++;
			if(k==p[i]+1)break;
		}
		
		printf("Supervisor %d with Employee %d\n",i+1,j+1);
		sign[j]=0;
	}
}



void search(int b,int sn,int e0[20][20],int value)
{
	int temp,ee[20][20];
	if(sn==0)print();
	
	for(p[b]=0;p[b]<sn;p[b]++)
	{
		del_copy(ee,e0,0,p[b],sn);
		temp=value+maxvaluematch(sn-1,ee)+e0[0][p[b]];
		if(temp==v)
			search(b+1,sn-1,ee,value+e0[0][p[b]]);

	}
	return;
}



int main()
{
	int t,i,j,s,k;
	cin>>t;
//	freopen("txt.txt","w",stdout);
	for(k=0;k<t;k++)
	{
		cin>>n;
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			e[i][j]=0;

		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			cin>>s;
		//	e[i][s-1]+=-j;
			e[s-1][i]+=-j;
		}

		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			cin>>s;
		//	e[s-1][i]+=-j;
			e[i][s-1]+=-j;
		}

		v=maxvaluematch(n,e);
		
		
		printf("Data Set %d, Best average difference: %.6lf\n",k+1,(double)-v/2/n);
		
		cas=0;
		search(0,n,e,0);
		printf("\n");
	}
	return 0;
}