Description
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同
的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最
小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
solution
正解：费用流
这题建图比较巧妙，首先一个人可以修多辆车，我们可以考虑拆点，由于一个点修车的顺序是不确定的，费用也不确定，我们可以用到未来费用思想，在当前考虑对之后的影响：
我们容易发现：如果当前车在第 (k) 个被修，那么之后的每一个顾客都要等 (k) 分钟，所以对答案的总贡献是 ((n-k)*w[i])，(w[i]) 为第 (i) 辆车被修的时间，所以我们直接 O(n^3)连边:
点 ((i,k)->j) 表示第 (i) 个人第 (k) 个修的车是 (j)，把未来费用作为边的费用即可，容量都为1，因为每一个人一个时刻只能修一辆车
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <queue>
#include <cmath>
#define RG register
#define il inline
#define iter iterator
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
#define id(x,y) (((x)-1)*m+(y))
using namespace std;
const int N=65,M=2000005,P=5005;
int n,m,num=1,head[P],to[M],nxt[M],dis[M],map[N][N],c[M],S=0,T;
il void link(int x,int y,int z,int ct){
nxt[++num]=head[x];
to[num]=y;dis[num]=z;c[num]=ct;
head[x]=num;
}
il void addedge(int x,int y,int z,int ct){link(x,y,z,ct);link(y,x,0,-ct);}
queue<int>q;bool vis[P];int pre[P],inf,ans=0,f[P];
bool spfa(){
while(!q.empty())q.pop();
memset(f,127/3,sizeof(f));
memset(vis,0,sizeof(vis));
inf=f[0];q.push(S);f[S]=0;vis[S]=1;
RG int x,u,i;
while(!q.empty()){
x=q.front();q.pop();
for(i=head[x];i;i=nxt[i]){
if(dis[i]<=0)continue;
u=to[i];
if(f[x]+c[i]<f[u]){
f[u]=f[x]+c[i];pre[u]=i;
if(!vis[u])vis[u]=1,q.push(u);
}
}
vis[x]=0;
}
if(f[T]!=inf)ans+=f[T];
return f[T]!=inf;
}
void upd(){
int x=T;
while(x){
dis[pre[x]]--;
dis[pre[x]^1]++;
x=to[pre[x]^1];
}
}
void Mincost(){while(spfa())upd();}
void work()
{
scanf("%d%d",&n,&m);
int sta=n*m;T=n*m+m+1;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&map[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
addedge(S,id(i,j),1,0);
for(int k=1;k<=m;k++)
addedge(id(i,j),sta+k,1,j*map[k][i]);
}
for(int i=1;i<=m;i++)addedge(sta+i,T,1,0);
Mincost();
printf("%.2lf
",1.0*ans/m);
}
int main()
{
work();
return 0;
}