题意很明确,,就是一个二分图,求最优匹配,,蛋疼的是第二个要求,有多少个跟原来的匹配,就是优先选择原来的匹配,跟hdu 2853一样,将边的权值扩大1000倍,原来的匹配边+1,求得的值sum/1000就ok了,原来的匹配个数=sum%1000。。。。用费用流做效果不好,耗时太多
#include<stdio.h> #include<queue> #include<string.h> const int N=110; const int inf=0x3fffffff; using namespace std; int map[N][N],lx[N],ly[N],sx[N],sy[N],d[N],n,match[N],tch[N]; struct node { int w,hp,cut; }P[100],R[100]; int find(int x) { sx[x]=1; for(int i=1;i<=n;i++) { if(sy[i]==1)continue; int temp=lx[x]+ly[i]-map[x][i]; if(temp==0) { sy[i]=1; if(match[i]==-1||find(match[i])==1) { match[i]=x; return 1; } } else d[i]=d[i]>temp?temp:d[i]; } return 0; } int KM() { int i,j,k,min,sum; memset(ly,0,sizeof(ly)); memset(match,-1,sizeof(match)); for(i=1;i<=n;i++) { lx[i]=map[i][1]; for(j=2;j<=n;j++) if(lx[i]<map[i][j]) lx[i]=map[i][j]; } for(i=1;i<=n;i++) { for(j=1;j<=n;j++) d[j]=inf; while(1) { memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy)); if(find(i)==1)break; min=inf; for(k=1;k<=n;k++) if(sy[k]==0&&min>d[k]) min=d[k]; for(j=1;j<=n;j++) if(sx[j]==1)lx[j]-=min; for(j=1;j<=n;j++) if(sy[j]==1)ly[j]+=min; } } sum=0; for(i=1;i<=n;i++) sum+=map[match[i]][i]; if(sum<0)return -1; return sum; } int main() { int i,j,x,y; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) map[i][j]=-inf; for(i=1;i<=n;i++) scanf("%d",&P[i].w); for(i=1;i<=n;i++) scanf("%d",&P[i].hp); for(i=1;i<=n;i++) scanf("%d",&R[i].hp); for(i=1;i<=n;i++) scanf("%d",&P[i].cut); for(i=1;i<=n;i++) scanf("%d",&R[i].cut); for(i=1;i<=n;i++) { for(j=1;j<=n;j++) { x=P[i].hp/R[j].cut; if(P[i].hp%R[j].cut) x++; if(P[i].cut*x>=R[j].hp) map[i][j]=P[i].w*1000; else map[i][j]=-P[i].w*1000; } map[i][i]+=1; } y=KM(); if(y==-1)printf("Oh, I lose my dear seaco!\n"); else printf("%d %.3f%%\n",y/1000,(y%1000)*100.0/n); } return 0; }