首页 > 代码库 > hdu3315 /最大权最佳匹配(最大权下尽量不改变次序)(有权田忌赛马类问题)/费用流
hdu3315 /最大权最佳匹配(最大权下尽量不改变次序)(有权田忌赛马类问题)/费用流
题意:2个人比赛,每场比赛有得分,每场每人派一支圣兽( brute ,字典翻译为畜生,感觉这里不太符╮(╯▽╰)╭),有攻击力和血条。。。一堆规则。。。
合理安排,让1号人获得最大分数,并尽量不要改变原来出场顺序(1,2,3.。。n),并求出相似度(没改变的场数/n)
思路:显然建二分图,赢的话就连负边,输就是正边,x->y,,再跑 s->t费用流,按题意关键是如何在最大费用情况下,尽量流 i-->i`的边,:扩大主要费用法!费用扩大比n稍大倍,这里扩大100倍,那么如果是 i-->i`的边,就费用再-1(最多-n,也不影响总费用),所以最后结果取负后,如果ans<100(相当于是费用流0)输,结果为ans/100,取i-->i`的边个数为 ans%100(自然)。
ps:还调了半天,因为题意没有理解到位!第i场比赛分数,按1号人物的圣兽编号为准!以后一定先看样例!
#include<cstdio> #include<iostream> #include<queue> #include<cstring> using namespace std; const int maxv=200; const int maxe=200*200*2+800; const int inf=0x3f3f3f3f; int nume=0;int e[maxe][4];int head[maxv]; int n,m,k; void inline adde(int i,int j,int c,int w) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume][2]=c;e[nume++][3]=w; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume][2]=0;e[nume++][3]=-w; } int inq[maxv];int pre[maxv];int prv[maxv]; int d[maxv]; int val[maxv];int hi[maxv];int pi[maxv];int ai[maxv];int bi[maxv]; //val该圣兽对应分数(以我方为标准) pi:我方圣兽血,hi敌血,ai我攻击力,bi敌攻击力 bool spfa(int &sum,int &flow) { int s=2*n,t=2*n+1; for(int i=0;i<=t;i++) { inq[i]=0; d[i]=inf; } queue<int>q; q.push(s); inq[s]=1; d[s]=0; while(!q.empty()) { int cur=q.front(); q.pop(); inq[cur]=0; for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(e[i][2]>0&&d[cur]+e[i][3]<d[v]) { d[v]=d[cur]+e[i][3]; pre[v]=i; prv[v]=cur; if(!inq[v]) { q.push(v); inq[v]=1; } } } } if(d[t]==inf)return 0; int cur=t; int minf=inf; while(cur!=s) { int fe=pre[cur]; minf=e[fe][2]<minf?e[fe][2]:minf; cur=prv[cur]; } cur=t; while(cur!=s) { e[pre[cur]][2]-=minf; e[pre[cur]^1][2]+=minf; cur=prv[cur]; } flow+=minf; sum+=d[t]*minf; return 1; } int mincost(int &flow) { int sum=0; while(spfa(sum,flow)); return sum; } void init() { nume=0; for(int i=0;i<=n*2+2;i++) head[i]=-1; } bool getres(int xph,int xf,int yph,int yf) //使用该匹配能不能赢 { int count1,count2; if(xph%yf!=0) count1=xph/yf+1; else count1=xph/yf; if(yph%xf!=0) count2=yph/xf+1; else count2=yph/xf; if(count1>=count2)return 1; else return 0; } void read_build() { for(int j=0;j<n;j++) scanf("%d",&val[j]); for(int j=0;j<n;j++) scanf("%d",&hi[j]); for(int j=0;j<n;j++) scanf("%d",&pi[j]); for(int j=0;j<n;j++) scanf("%d",&ai[j]); for(int j=0;j<n;j++) scanf("%d",&bi[j]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { if(getres(hi[i],ai[i],pi[j],bi[j])) { if(i!=j) // 相等情况下,费用-1 adde(i,j+n,1,-val[i]*100); else adde(i,j+n,1,-val[i]*100-1); } else { if(i!=j) adde(i,j+n,1,val[i]*100); else adde(i,j+n,1,val[i]*100-1); } } for(int i=0;i<n;i++) { adde(2*n,i,1,0); adde(i+n,2*n+1,1,0); } /* for(int i=0;i<=2*n+1;i++) for(int j=head[i];j!=-1;j=e[j][1]) { printf("%d->%d:f %dw %d\n",i,e[j][0],e[j][2],e[j][3]); }*/ } int main() { while(~scanf("%d",&n)&&n!=0) { init(); read_build(); int flow=0; int ans=-mincost(flow); if(ans<100) //这里是<100,因为现在已经取反! printf("Oh, I lose my dear seaco!\n"); else printf("%d %.3f%%\n",ans/100,(ans%100)*1.0/n*100); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。