BZOJ 1070, 修车

2019-11-10 21:31:39

字体：大中小

来源：转载

供稿：网友

PRoblem

传送门

Mean

某汽车维修中心有m位技术人员，有n辆汽车待修理。不同的技术人员修理不同车辆耗时不同。最小化平均等待时间。

Analysis

经典的最小费用最大流。设第j位技术人员修理第i辆汽车耗时为w[i,j] 。将技术人员拆成n个点，每个点向汽车连容量为1的边，第k个点所连边费用为k×w[i,j]，表示倒数第k个修理该车则对总等待时间贡献k×w[i,j]。再由源点想技术人员，汽车向汇点分别连容量为1，费用为0的边即可。

Code

#include<cstdio>const int N=605,M=66005,INF=~0U>>2;int i,m,n,s,t,tmp,x,cnt,ans,l,r,ed=1,u[M],v[M],c[M],co[M],nxt[M],q[M],g[N],f[N],d[N];bool in[N];void add(int x,int y,int z,int zo){ u[++ed]=x,v[ed]=y,c[ed]=z,co[ed]=zo,nxt[ed]=g[x],g[x]=ed; u[++ed]=y,v[ed]=x,c[ed]=0,co[ed]=-zo,nxt[ed]=g[y],g[y]=ed;}bool SPFA(){ for(i=1;i<=t;i++) d[i]=INF,in[i]=0; in[s]=1,q[l=r=M>>1]=s; while(l<=r){ int x=q[l++]; if(x==t) continue; for(i=g[x];i;i=nxt[i]) if(c[i] && d[v[i]]>d[x]+co[i]){ d[v[i]]=d[x]+co[i]; f[v[i]]=i; if(!in[v[i]]){ if(d[v[i]]<d[q[l]]) q[--l]=v[i]; else q[++r]=v[i]; in[v[i]]=1; } } in[x]=0; } return d[t]<INF;}int main(){ scanf("%d%d",&m,&n); tmp=n*m,t=tmp+n+1; for(i=1;i<=n;i++){ add(i+tmp,t,1,0); for(int j=0;j<m;j++){ int p=j*n; scanf("%d",&x); for(int k=1;k<=n;k++) add(p+k,i+tmp,1,k*x); } } for(i=1;i<=tmp;i++) add(s,i,1,0); while(SPFA()){ for(tmp=INF,i=t;i!=s;i=u[f[i]]) if(tmp>c[f[i]]) tmp=c[f[i]]; for(ans+=d[i=t]*tmp;i!=s;i=u[f[i]]) c[f[i]]-=tmp,c[f[i]^1]+=tmp; } printf("%.2f",ans/(double)n); return 0;}

上一篇：设计模式——单例模式（Singleton）

下一篇：LintCode Search Graph Node

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注