首页 > 代码库 > BZOJ1070 修车-费用网络流
BZOJ1070 修车-费用网络流
http://www.lydsy.com/JudgeOnline/problem.php?id=1070
Description
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同
的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最
小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
Input
第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人
员维修第i辆车需要用的时间T。
Output
最小平均等待时间，答案精确到小数点后2位。
HINT
数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)
//.............
1 #include<iostream> 2 #include<vector> 3 #include<cstring> 4 #include<cstdio> 5 #include<queue> 6 using namespace std; 7 const int maxn=3000; 8 const int inf=1<<30; 9 struct Edge{10 int from,to,cap,flow,cost;11 };12 struct MCMF{13 int n,m,s,t;14 vector<Edge> edges;15 vector<int> G[maxn];16 int inq[maxn];17 int d[maxn];18 int p[maxn];19 int a[maxn];20 void init(int n){21 this->n=n;22 for(int i=1;i<=n;i++) G[i].clear();23 edges.clear();24 }25 void addEdge(int from,int to,int cap,int cost){26 edges.push_back((Edge){from,to,cap,0,cost});27 edges.push_back((Edge){to,from,0,0,-cost});28 m=edges.size();29 G[from].push_back(m-2);30 G[to].push_back(m-1);31 }32 bool BF(int s,int t,int& flow,int& cost){33 for(int i=1;i<=n;i++) d[i]=inf;34 memset(inq,0,sizeof(inq));35 d[s]=0;inq[s]=1;p[s]=0;a[s]=inf;36 37 queue<int> Q;38 Q.push(s);39 while(!Q.empty()){40 int u=Q.front();Q.pop();41 inq[u]=0;42 for(int i=0;i<G[u].size();i++){43 Edge& e=edges[G[u][i]];44 if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){45 d[e.to]=d[u]+e.cost;46 p[e.to]=G[u][i];47 a[e.to]=min(a[u],e.cap-e.flow);48 if(!inq[e.to]){49 Q.push(e.to);50 inq[e.to]=1;51 }52 }53 }54 }55 if(d[t]==inf) return false;56 flow+=a[t];57 cost+=d[t]*a[t];58 int u=t;59 while(u!=s){60 edges[p[u]].flow+=a[t];61 edges[p[u]^1].flow-=a[t];62 u=edges[p[u]].from;63 }64 return true;65 }66 int MinCost(int s,int t){67 int flow=0,cost=0;68 while(BF(s,t,flow,cost));69 return cost;70 }71 };72 MCMF solver;73 int t[61][10];74 int main()75 {76 int n,m;77 scanf("%d %d",&m,&n);78 solver.init(2+n*(m+1));79 for(int i=1;i<=n;++i)80 for(int j=1;j<=m;++j)81 scanf("%d",&t[i][j]);82 for(int i=1;i<=n;++i)83 solver.addEdge(1,1+i,1,0);84 for(int i=1;i<=n*m;++i)85 solver.addEdge(1+n+i,2+n+n*m,1,0);86 for(int i=1;i<=n;i++){87 for(int j=1;j<=m;j++){88 int T=t[i][j];89 for(int k=1;k<=n;k++)90 solver.addEdge(1+i,1+n+(j-1)*n+k,1,T*k);91 }92 }93 printf("%.2lf",((double)solver.MinCost(1,2+n*(m+1)))/n);94 return 0;95 }
BZOJ1070 修车-费用网络流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。