$bzoj1070-SCOI2007$ 修车 费用流
- 题面描述
- 同一时刻有\(N\)位车主带着他们的爱车来到了汽车维修中心。维修中心共有\(M\)位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这\(M\)位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
- 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
- 输入格式
- 第一行有两个\(m,n\)，表示技术人员数与顾客数。 接下来\(n\)行，每行\(m\)个整数。第\(i+1\)行第\(j\)个数表示第\(j\)位技术人员维修第\(i\)辆车需要用的时间\(T\)
- 输出格式
- 最小平均等待时间，答案精确到小数点后\(2\)位。
- 题解
- 考虑对于单个技术人员\(j\)，第一个前来向其修车的车主\(i\)，等候时间为\(time_{i,j}\)，第二个前来修车的车主\(k\)，等候时间为\(time_{j,i}+time_{k,i}\cdots\)以此类推。每个修车时间对总等候时间的贡献为\(time_{x,i}*k_x\)，\(k_x\)表示是倒数第几位前来向技术人员\(i\)修车的车主
- 由此启发，将每个技术人员拆成\(n\)个点，第\(i\)个点表示这个技术人员修的倒数第\(n-i+1\)辆车
- 第\(k\)位车主，向第\(x\)位技术人员第\(y\)个点连\(cap=1,cost=(n-y+1)*time_{x,k}\)的边
- 总边数\(M=O(n^2m)\)，总点数\(N=O(nm)\)，\(dinic\)总复杂度\(O(n^2m^2\sqrt{n^2m})=O(n^3m^2\sqrt{m})\)
- 直接跑费用流即可
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int MAXN=1e3+6;
const int MAXM=1e6+6;
const int inf=1e9;
int edge=1,nex[MAXM],head[MAXN],tail[MAXM],w[MAXM],r[MAXM];
int n,m,S,T;
int d[MAXN],h[MAXN];
int preu[MAXN],pree[MAXN];
bool use[MAXN];
int a[MAXN][MAXN];
struct rq{
int u,d;
bool operator < (const rq& b) const{
return d>b.d;
}
};
priority_queue<rq> q;
void add(int u,int v,int R,int W){
edge++,nex[edge]=head[u],head[u]=edge,tail[edge]=v,r[edge]=R,w[edge]=W;
}
void ins(int u,int v,int R,int W){
add(u,v,R,W); add(v,u,0,-W);
}
bool dij(){
for (int i=1;i<=T;i++) d[i]=inf,use[i]=0;
d[S]=0; q.push((rq){S,0});
while (!q.empty()){
rq u=q.top(); q.pop();
if (use[u.u]) continue;
use[u.u]=1;
for (int e=head[u.u];e;e=nex[e]){
int v=tail[e];
int W=h[u.u]+w[e]-h[v];
if (d[v]>d[u.u]+W&&r[e]>0){
d[v]=d[u.u]+W; preu[v]=u.u; pree[v]=e;
q.push((rq){v,d[v]});
}
}
}
return d[T]<inf;
}
int main(){
scanf("%d%d",&n,&m);
S=m+n*m+1; T=S+1;
for (int i=1;i<=m;i++){
for (int j=1;j<=n;j++) scanf("%d",&a[i][j]);
}
for (int i=1;i<=m;i++) ins(S,i,1,0);
for (int i=m+1;i<=n*m+m;i++) ins(i,T,1,0);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
for (int k=1;k<=m;k++) ins(k,m+(i-1)*m+j,1,a[k][i]*j);
}
}
int flow=0,cost=0;
while (dij()){
// cout<<"in"<<endl;
for (int i=1;i<=T;i++) h[i]+=d[i];
int res=inf;
for (int u=T;u!=S;u=preu[u]){
int v=preu[u],e=pree[u];
res=min(res,r[e]);
}
// cout<<res<<" "<<h[T]<<endl;
flow+=res; cost+=res*h[T];
for (int u=T;u!=S;u=preu[u]){
int v=preu[u],e=pree[u];
r[e]-=res; r[e^1]+=res;
}
}
printf("%.2lf\n",(double)cost/(double)m);
return 0;
}
更多精彩
