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