[SCOI2007]修车

题目描述
同一时刻有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)

看到这道题应该会要么想到费用流，要么想到二分图权值匹配，都是可以的。。只要保证吗，每辆车都被匹配就行了。

我们怎么保证呢？

当然是最大流了，然后等待时间最小就用最小费用保证。

考虑建图：

对于每个技术人员，我们可以把他，拆成 n * m个，然后权值是工人时间段编号 * 输入的时间，表示需要等待的时间，流量就是1。

再加入超级源点和超级汇点就可以了。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
const int inf=0x3f3f3f3f;
int m,n,s,t,d[N],v[N],e[N];
int head[N],nex[N],to[N],w[N],flow[N],tot=1;
inline void ade(int a,int b,int c,int d){
	to[++tot]=b; w[tot]=d; flow[tot]=c; nex[tot]=head[a]; head[a]=tot;
}
inline void add(int a,int b,int c,int d){
	ade(a,b,c,d);	ade(b,a,0,-d);
}
int spfa(){
	memset(d,inf,sizeof d);	d[s]=0;	queue<int> q;	q.push(s);
	int vis[N]={0};	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();	vis[u]=0;
		for(int i=head[u];i;i=nex[i]){
			if(flow[i]&&d[to[i]]>d[u]+w[i]){
				d[to[i]]=d[u]+w[i];
				v[to[i]]=u; e[to[i]]=i;
				if(!vis[to[i]])	q.push(to[i]),vis[to[i]]=1;
			}
		}
	}
	return d[t]!=inf;
}
void EK(){
	int res=0;
	while(spfa()){
		int mi=inf;
		for(int i=t;i!=s;i=v[i])	mi=min(mi,flow[e[i]]);
		for(int i=t;i!=s;i=v[i])	flow[e[i]]-=mi,flow[e[i]^1]+=mi;
		res+=mi*d[t];
	}
	printf("%.2lf\n",(double)(res*1.0/n));
}
signed main(){
	cin>>m>>n;	s=0;	t=n+n*m+1;
	for(int i=1;i<=n;i++){
		add(s,i,1,0);
		for(int j=1;j<=m;j++){
			int x;	cin>>x;	
			for(int k=1;k<=n;k++){
				add(i,n+k+(j-1)*n,1,x*k);
			}
		}
	}
	for(int i=1;i<=m;i++)	for(int j=1;j<=n;j++)	add(n+j+(i-1)*n,t,1,0);
	EK();
	return 0;
}