首页 > 代码库 > [BZOJ 1070][SCOI2007]修车(费用流)
[BZOJ 1070][SCOI2007]修车(费用流)
Description
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员,不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序,使得顾客平均等待的时间最小。 说明:顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
Solution
非常经典的建图方式,将每一位技术人员拆成n个点分别他是表示倒数第几个修车的,倒数第k个修车的技术人员对所有在等待的人的贡献是tim[i][j]*k
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>#include<algorithm>#include<queue>#define INF 0x3f3f3f3f#define dot(x,y) (x+(y-1)*m) //维修人员x在倒数第y的位置using namespace std;int s,t,n,m,head[1005],cnt=0,tim[70][10];int dis[5005],f[5005],pre[5005];bool inq[5005];int read(){ int x=0,f=1;char c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}struct Node{ int next,from,to,cap,w;}Edges[500005];void addedge(int u,int v,int c,int w){ Edges[cnt].next=head[u]; head[u]=cnt; Edges[cnt].from=u,Edges[cnt].to=v; Edges[cnt].w=w; Edges[cnt++].cap=c;}void insert(int u,int v,int c,int w){ addedge(u,v,c,w); addedge(v,u,0,-w);}queue<int>q;int MCMF(){ int flow=0,cost=0; while(1) { memset(dis,0x3f,sizeof(dis)); memset(f,0,sizeof(f)); q.push(s),pre[s]=-1,inq[s]=1,dis[s]=0,f[s]=INF; while(!q.empty()) { int u=q.front(); q.pop(),inq[u]=0; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(Edges[i].cap>0&&dis[v]>dis[u]+Edges[i].w) { dis[v]=dis[u]+Edges[i].w; f[v]=min(f[u],Edges[i].cap); pre[v]=i; if(!inq[v])q.push(v),inq[v]=1; } } } if(dis[t]==INF)break; flow+=f[t],cost+=dis[t]*f[t]; int p=t; while(pre[p]!=-1) { Edges[pre[p]].cap-=f[t]; Edges[pre[p]^1].cap+=f[t]; p=Edges[pre[p]].from; } } return cost;}int main(){ memset(head,-1,sizeof(head)); m=read(),n=read(),s=0,t=n*m*2+1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { insert(dot(j,i),t,1,0); tim[i][j]=read(); //第i辆车被第j位维修员维修的时间 tim[i][j] for(int k=1;k<=n;k++) insert(n*m+i,dot(j,k),1,tim[i][j]*k); } for(int i=1;i<=n;i++)insert(s,n*m+i,1,0); printf("%.2lf\n",(double)MCMF()/n); return 0;}
[BZOJ 1070][SCOI2007]修车(费用流)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。