BZOJ 1070, 修車

2019-11-10 22:42:27

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

PRoblem

傳送門

Mean

某汽車維修中心有m位技術(shù)人員，有n輛汽車待修理。不同的技術(shù)人員修理不同車輛耗時不同。最小化平均等待時間。

Analysis

經(jīng)典的最小費(fèi)用最大流。設(shè)第j位技術(shù)人員修理第i輛汽車耗時為w[i,j] 。將技術(shù)人員拆成n個點(diǎn)，每個點(diǎn)向汽車連容量為1的邊，第k個點(diǎn)所連邊費(fèi)用為k×w[i,j]，表示倒數(shù)第k個修理該車則對總等待時間貢獻(xiàn)k×w[i,j]。再由源點(diǎn)想技術(shù)人員，汽車向匯點(diǎn)分別連容量為1，費(fèi)用為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;}

上一篇：JVM運(yùn)行數(shù)據(jù)環(huán)境

下一篇：多個源程序組成程序編譯問題