| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:题目的意思就是求所有最优匹配,应该还是挺明确的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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator