题意:
有一个叫My Brute的游戏...现在starvae和xingxing来PK..每轮starve与xingxing有相应的攻击力以及血量..若某一轮starve赢了可以获得一定的分数..否则要减去这么多分数..现在starve可以交换自己每次出场的状态...问starve能获得的最大分数..并且在这个最大分数上..与初始顺序的相似度要最大...
题解:
对于这类要在一个值达到最值..保持另一个值最值的问题..一般采用偏移量..比如这题..因为人数最多90..所以把偏移量设置为100..那么对于得到分数.都乘以100..对于影响相似度的..就直接+1...这样最后的结果..分数就是ans/100...相似度就是ans%100....也挺好理解的..
那么这题用最大费用最大流或者KM都ok了..话说费用流的效率是KM的30倍啊....
最大费用最大流(906ms):
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<math.h> #include<queue> #define MAXN 505 #define MAXM 8000005 #define oo 1000000007 #define ll long long using namespace std; struct MCMF { struct node { int x,y,c,v,next; }line[MAXM]; int Lnum,_next[MAXN],pre[MAXN],dis[MAXN],flow,cost; bool inqueue[MAXN]; void initial(int n) { Lnum=-1; for (int i=0;i<=n;i++) _next[i]=-1; } void addline(int x,int y,int c,int v) { line[++Lnum].next=_next[x],_next[x]=Lnum; line[Lnum].x=x,line[Lnum].y=y,line[Lnum].c=c,line[Lnum].v=v; line[++Lnum].next=_next[y],_next[y]=Lnum; line[Lnum].x=y,line[Lnum].y=x,line[Lnum].c=0,line[Lnum].v=-v; } bool SPFA(int s,int e) { int x,k,y; queue<int> Q; while (!Q.empty()) Q.pop(); memset(dis,0x7f,sizeof(dis)); memset(inqueue,false,sizeof(inqueue)); Q.push(s); dis[s]=0,pre[s]=-1; while (!Q.empty()) { x=Q.front(),Q.pop(),inqueue[x]=false; for (k=_next[x];k!=-1;k=line[k].next) if (line[k].c) { y=line[k].y; if (dis[y]>dis[x]+line[k].v) { dis[y]=dis[x]+line[k].v; pre[y]=k; if (!inqueue[y]) { inqueue[y]=true; Q.push(y); } } } } if (dis[e]>oo) return false; flow=oo,cost=0; for (k=pre[e];k!=-1;k=pre[line[k].x]) flow=min(flow,line[k].c),cost+=line[k].v; cost*=flow; for (k=pre[e];k!=-1;k=pre[line[k].x]) line[k].c-=flow,line[k^1].c+=flow; return true; } void MinCostMaxFlow(int s,int e,int &Aflow,int &Acost) { Aflow=0,Acost=0; while (SPFA(s,e)) { Aflow+=flow; Acost+=cost; } } }T; struct node { int V,H,P,A,B; }W[105]; bool beat(node a1,node a2) { int p1=a2.P/a1.A,p2=a1.H/a2.B; if (a2.P%a1.A) p1++; if (a1.H%a2.B) p2++; return p1<=p2; } int main() { int n,i,j,t,s,e; while (~scanf("%d",&n) && n) { s=n<<2,e=s+1,T.initial(e); for (i=1;i<=n;i++) scanf("%d",&W[i].V),T.addline(s,i<<1,1,0); for (i=1;i<=n;i++) scanf("%d",&W[i].H),T.addline(i<<1|1,e,1,0); for (i=1;i<=n;i++) scanf("%d",&W[i].P); for (i=1;i<=n;i++) scanf("%d",&W[i].A); for (i=1;i<=n;i++) scanf("%d",&W[i].B); for (i=1;i<=n;i++) for (j=1;j<=n;j++) { if (i!=j) t=0; else t=1; if (beat(W[i],W[j])) T.addline(i<<1,j<<1|1,1,-W[i].V*100-t); else T.addline(i<<1,j<<1|1,1,W[i].V*100-t); } int Af,Ac; T.MinCostMaxFlow(s,e,Af,Ac),Ac=-Ac; if (Ac<=0) printf("Oh, I lose my dear seaco!\n"); else printf("%d %.3f%%\n",Ac/100,Ac%100*100.0/n); } return 0; }
二分图最大权最大匹配KM(31ms):
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<math.h> #include<queue> #define MAXN 105 #define MAXM 50005 #define oo 1<<30 #define ll long long using namespace std; //--------------------n为两侧的个数..w[][]为关系矩阵初始为-inf------------------- int n; int linker[MAXN],lx[MAXN],ly[MAXN],slack[MAXN]; int visx[MAXN],visy[MAXN],w[MAXN][MAXN]; int v[MAXN],h[MAXN],p[MAXN],a[MAXN],b[MAXN]; int DFS(int x){ visx[x]=1; for(int y=1;y<=n;y++){ if(visy[y]) continue; int tmp=lx[x]+ly[y]-w[x][y]; if(tmp==0){ visy[y]=1; if(linker[y]==-1 || DFS(linker[y])){ linker[y]=x; return 1; } }else if(slack[y]>tmp){ //不在相等子图中slack 取最小的 slack[y]=tmp; } } return 0; } int KM(){ int i,j; memset(linker,-1,sizeof(linker)); memset(ly,0,sizeof(ly)); for(i=1;i<=n;i++) //lx初始化为与它关联边中最大的 for(j=1,lx[i]=-oo;j<=n;j++) if(w[i][j]>lx[i]) lx[i]=w[i][j]; for(int x=1;x<=n;x++){ for(i=1;i<=n;i++) slack[i]=oo; while(1){ memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if(DFS(x)) break; int d=oo; for(i=1;i<=n;i++) if(!visy[i] && d>slack[i]) d=slack[i]; for(i=1;i<=n;i++) if(visx[i]) lx[i]-=d; for(i=1;i<=n;i++) if(visy[i]) ly[i]+=d; else slack[i]-=d; } } int res=0; for(i=1;i<=n;i++){ if(linker[i]==-1 || w[linker[i]][i]==-oo) return -1; res+=w[linker[i]][i]; } return res; } //-------------------------------------------------------- int V[105],H[105],P[105],A[105],B[105]; int main() { int i,j; while (~scanf("%d",&n) && n) { for (i=1;i<=n;i++) scanf("%d",&V[i]); for (i=1;i<=n;i++) scanf("%d",&H[i]); for (i=1;i<=n;i++) scanf("%d",&P[i]); for (i=1;i<=n;i++) scanf("%d",&A[i]); for (i=1;i<=n;i++) scanf("%d",&B[i]); memset(w,0,sizeof(w)); for (i=1;i<=n;i++) for (j=1;j<=n;j++) { if (((P[j]-1)/A[i])<=((H[i]-1)/B[j])) w[i][j]=V[i]*100; else w[i][j]=-V[i]*100; if (i==j) w[i][j]++; } int ans=KM(); if (ans<=0) printf("Oh, I lose my dear seaco!\n"); else printf("%d %.3f%%\n",ans/100,ans%100/(1.0*n)*100); } return 0; }