题目描述
同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。
说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。
输入输出格式
输入格式：第一行有两个数M,N，表示技术人员数与顾客数。
接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。
输出格式：最小平均等待时间，答案精确到小数点后2位。
输入输出样例
输入样例#1：
2 2
3 2
1 4
输出样例#1：
1.50
说明
(2<=M<=9,1<=N<=60), (1<=T<=1000)
Solution：
本题贼有意思的费用流。
题意要使平均等待时间最小，等价于使等待时间总和最小。
考虑一个修理工处理这n辆车，设n辆车处理顺序为$a_1,a_2…a_n$，则等待总时间$=w_1*n+w_2*(n-1)+…w_n*1$，不难发现每辆车在每个修理工处都会有$n$种不同贡献的状态，且每个状态最多只能修一辆车，这样的带权有上下界限制的问题（数据范围还OK），当然就是费用流模型啦。
我们建立一个完全二分图，$n$辆车作为左部，将$m$个修理工，每个都拆成$n$个点，作为右部，表示该修理工的每次修理状态，由每辆车向每个修理工的不同状态连权值$1$费用$w_i*k$的边。
附加源点和汇点，跑最小费用最大流就好了。
时间复杂度：因为$n$次增广，每次增广最多访问$n^2*m$条边，实际上spfa还有常数$k$，所以最坏$O(k*m^2*n^2)$（反正能过就行~^-^~，分析这个是为本题加强版做铺垫）。
代码：
/*Code by 520 -- 8.27*/ #include<bits/stdc++.h> #define il inline #define ll long long #define RE register #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++) #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--) #define debug printf("%d %s ",__LINE__,__FUNCTION__) using namespace std; const int N=100005,inf=233333333; int s,t,n,m,maxn[N],pre[N],dis[N]; int to[N],net[N],w[N],c[N],h[N],cnt=1; int maxf,maxc; bool vis[N]; il void add(int u,int v,int fl,int co){ to[++cnt]=v,net[cnt]=h[u],w[cnt]=fl,c[cnt]=co,h[u]=cnt; to[++cnt]=u,net[cnt]=h[v],w[cnt]=0,c[cnt]=-co,h[v]=cnt; } queue<int>q; il bool spfa(){ For(i,1,t) dis[i]=inf; dis[s]=0,maxn[s]=inf,q.push(s); while(!q.empty()){ RE int u=q.front();q.pop();vis[u]=0; for(RE int i=h[u];i;i=net[i]) if(dis[to[i]]>dis[u]+c[i]&&w[i]){ dis[to[i]]=dis[u]+c[i],pre[to[i]]=i, maxn[to[i]]=min(maxn[u],w[i]); if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]); } } return dis[t]!=inf; } il void update(){ int p=t; while(p!=s){ RE int i=pre[p]; w[i]-=maxn[t],w[i^1]+=maxn[t]; p=to[i^1]; } maxf+=maxn[t],maxc+=maxn[t]*dis[t]; } il void init(){ scanf("%d%d",&m,&n),t=n*m+n+1; For(i,1,n) { add(s,i,1,0); For(j,1,m) { RE int p;scanf("%d",&p); For(k,1,n) add(i,j*n+k,1,k*p); add(j*n+i,t,1,0); } } while(spfa())update(); printf("%.2lf",maxc*1.0/n); } int main(){ init(); return 0; }