Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:题目的意思就是求所有最优匹配,应该还是挺明确的

Posted by javaman at 2005-06-29 22:24:53 on Problem 2400
In Reply To:题目的意思就是求所有最优匹配,应该还是挺明确的 Posted by:TN at 2005-06-29 22:17:13
我只想知道为什么错 我是直接搜索的 本来打算tle再改最优匹配

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>


using namespace std;

const int inf=2100000000;

typedef struct {
int p[150];
} PPP;


PPP pp;

int b[150][150],a[150][150];
bool mark[150];
int n,best;


vector<PPP> ans;
vector<PPP>::iterator yy;

int perm2num(int n,int *p){
	int i,j,ret=0,k=1;
	for (i=n-2;i>=0;k*=n-(i--))
		for (j=i+1;j<n;j++)
			if (p[j]<p[i])
				ret+=k;
	return ret;
}

void haveatry(int now,int dif) {
int i;
	if (best<dif)
		return;

	if (now==n) {

		if (best>dif)
			ans.clear();

		ans.push_back(pp);
		best=dif;
		return;
	}

	for (i=0;i<n;++i) {
		if (!mark[i]) {
			mark[i]=true;
			pp.p[now]=i;
			haveatry(now+1,dif+a[now][i]+b[i][now]);
			mark[i]=false;
		}
	}
}

int main() {
int z,zz,i,j,x;

	scanf("%d",&zz);
	for (z=1;z<=zz;++z) {
		ans.clear();
		if (z>1)
			printf("\n");
		scanf("%d",&n);

		for (i=0;i<n;++i) {
			for (j=0;j<n;++j) {
				scanf("%d",&x);
				a[i][x-1]=j;
			}
			
		}
		
		for (i=0;i<n;++i) {
			for (j=0;j<n;++j) {
				scanf("%d",&x);
				b[i][x-1]=j;
			}
		}
			
		best=inf;
		
		memset(mark,false,sizeof(mark));

		haveatry(0,0);
		printf("Data Set %d, Best average difference: %.6f\n",z,(double) best/2./n);

		for (yy=ans.begin();yy!=ans.end();++yy) {

			printf("Best Pairing %d\n",perm2num(n,yy->p)+1);

			for (i=0;i<n;++i)
				printf("Supervisor %d with Employee %d\n",i+1,yy->p[i]+1);
			
		
		}

	}
	return 0;
}



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator