BZOJ 1070, 修車

2019-11-11 00:52:49

字體：大中小

來源：轉載

供稿：網友

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;}

上一篇：hdu4405 Aeroplane chess【概率DP+期望問題】

下一篇：371. Sum of Two Integers