题目描述
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同
的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。输入
第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人
员维修第i辆车需要用的时间T。输出
最小平均等待时间，答案精确到小数点后2位。
从题意可以明显看出这是一道最小费用最大流，但显然不能直接把工人建在一边，汽车建在另一边，因为一个工人可能修多辆车，在修前面车的时候，后面车就要有等待时间。因此可以把每个工人拆开成n个工人，表示n个时间段。将这n辆汽车和n*m个工人连边，形成一个完全二分图。因为每辆修的车只会影响后面车的等待时间，所以对于每条边表示第i辆汽车，被第j个工人（题目中的工人，不是拆开的）在倒数第k个时间段（也就是说这辆车是这个工人倒数第k个修的车）修所耗费的时间是k*v[i][j]（因为是倒数第k个，所以包括他在内的后面k个车都要等待v[i][j]的时间）。 这样再跑最小费用最大流就可以求出最小时间了。
最后附上代码。
#include#include #include #include #include #include using namespace std;queue q;int d[1003];int f[1003];int v[100010];int c[100010];int vis[1003];int to[100010];int head[100010];int next[100010];int from[100010];int n,m;int S,T;int x;int tot=1;int ans=0;int INF=1<<30;int maxflow=0;void add(int x,int y,int z,int w){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y; c[tot]=z; v[tot]=w; from[tot]=x; tot++; next[tot]=head[y]; head[y]=tot; to[tot]=x; c[tot]=0; v[tot]=-w; from[tot]=y;}void result(){ int now=T; int flow=INF; while(now!=S) { flow=min(flow,c[f[now]]); now=from[f[now]]; } maxflow+=flow; ans+=d[T]*flow; now=T; while(now!=S) { c[f[now]]-=flow; c[f[now]^1]+=flow; now=from[f[now]]; }}bool SPFA(){ for(int i=1;i<=T;i++) { d[i]=INF; } d[S]=0; q.push(S); vis[S]=1; while(!q.empty()) { int now=q.front(); q.pop(); vis[now]=0; for(int i=head[now];i;i=next[i]) { if(!c[i]) { continue; } if(d[to[i]]>d[now]+v[i]) { d[to[i]]=d[now]+v[i]; f[to[i]]=i; if(!vis[to[i]]) { q.push(to[i]); vis[to[i]]=1; } } } } return d[T]!=INF;}void find_min(){ while(SPFA()) { result(); }}int main(){ scanf("%d%d",&m,&n); S=n*m+n+16; T=n*m+n+28; for(int i=1;i<=n;i++) { add(S,n*m+i,1,0); } for(int i=1;i<=n*m;i++) { add(i,T,1,0); } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf("%d",&x); for(int k=1;k<=n;k++) { add(n*m+i,(j-1)*n+k,1,k*x); } } } find_min(); printf("%.2lf",((double)ans)/((double)n)); return 0;}