题目:http://acm.hdu.edu.cn/showproblem.php?pid=3315
二分图的最优匹配。图很容易建立。再处理相似度的时候。把每个权值扩大100倍。然后再对i==j时 特殊标记。使他们的权值再++1。后面选择的时候就很容易挑出。按原匹配
匹配的个数。 100*(double)(res%100)/n。即可得到第二问。
下面是AC代码:
#include<cstdio> #include<string> #include<cstring> #include<iostream> #include<map> using namespace std; const int maxn = 105; const int INF = (1<<30)-1; int g[maxn][maxn]; int lx[maxn],ly[maxn]; int match[maxn]; bool visx[maxn],visy[maxn]; int slack[maxn]; int v[maxn],h[maxn],p[maxn],a[maxn],b[maxn]; int n,m; bool dfs(int cur){ visx[cur] = true; for(int y=1;y<=n;y++){ if(visy[y]) continue; int t=lx[cur]+ly[y]-g[cur][y]; if(t==0){ visy[y] = true; if(match[y]==-1||dfs(match[y])){ match[y] = cur; return true; } } else if(slack[y]>t){ slack[y]=t; } } return false; } int KM(){ memset(match,-1,sizeof(match)); memset(ly,0,sizeof(ly)); for(int i=1 ;i<=n;i++){ lx[i]=-INF; for(int j=1;j<=n;j++) if(g[i][j]>lx[i]) lx[i]=g[i][j]; } for(int x=1;x<=n;x++){ for(int i=1;i<=n;i++) slack[i]=INF; while(true){ memset(visx,false,sizeof(visx)); memset(visy,false,sizeof(visy)); if(dfs(x)) break; int d=INF; for(int i=1;i<=n;i++){ if(!visy[i]&&d>slack[i]) d=slack[i]; } for(int i=1;i<=n;i++){ if(visx[i]) lx[i]-=d; } for(int i=1;i<=n;i++){ if(visy[i]) ly[i]+=d; else slack[i]-=d; } } } int result = 0; for(int i = 1; i <=n ; i++){ if(match[i]>-1){ result += g[match[i]][i]; } } return result; } bool who_win(int x,int y){ int hp1=h[x]; int hp2=p[y]; int damage1=a[x], damage2=b[y]; while(1){ hp2=hp2-damage1; if(hp2<=0) return true; hp1=hp1-damage2; if(hp1<=0) return false; } } int main(){ int val,k; while(scanf("%d",&n)!=EOF){ if(n==0) break; for(int i=1;i<=n;i++) scanf("%d",&v[i]); for(int i=1;i<=n;i++) scanf("%d",&h[i]); for(int i=1;i<=n;i++) scanf("%d",&p[i]); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ if(who_win(i,j)){ g[i][j]=v[i]*100; if(i==j){ g[i][j]++; } } else{ g[i][j]=-v[i]*100; if(i==j) g[i][j]++; } } int res=KM(); int ans=res/100; if(ans>0){ printf("%d %.3lf%%\n",ans,100*(double)(res%100)/n); } else{ printf("Oh, I lose my dear seaco!\n"); } } return 0; }