[SCOI2007] 修车

题目描述

同一时刻有 \(N\) 位车主带着他们的爱车来到了汽车维修中心。

维修中心共有 \(M\) 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。

现在需要安排这 \(M\) 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。

说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

输入格式

第一行有两个数 \(M,N\)，表示技术人员数与顾客数。

接下来 \(N\) 行，每行 \(M\) 个整数。第 \(i+1\) 行第 \(j\) 个数表示第 \(j\) 位技术人员维修第 \(i\) 辆车需要用的时间 \(T_{i,j}\)。

输出格式

最小平均等待时间，答案精确到小数点后 \(2\) 位。

样例 #1

样例输入 #1

2 2
3 2
1 4

样例输出 #1

1.50

提示

对于 \(100\%\) 的数据，\(2\le M\le 9\)，\(1\le N\le 60\)，\(1\le T\le 10^3\)。

倒数第 \(i\) 个修的车，他的时间在总等待时间内会被计算 \(i\) 次。

把一个工人拆成 \(n\) 份，表示他倒数第 \(i\) 个修的车。然后给第 \(i\) 个车分配他是 \(k\) 人倒数第 \(j\) 个修的车，流量 1 费用 \(j\times t_{i,k}\)

#include<bits/stdc++.h> 
using namespace std;
const int N=2005,M=300005;
struct edge{
	int u,v,nxt,f,w;
}e[M];
struct node{
	int v,w;
	bool operator<(const node&n)const{
		return w>n.w;
	}
};
priority_queue<node>q;
int m,n,p[N],d[N],h[N],hd[N],T,e_num=1,l,r,v[N],t[65][10],ans;
void add_edge(int u,int v,int f,int w)
{
	e[++e_num]=(edge){u,v,hd[u],f,w};
	hd[u]=e_num;
	e[++e_num]=(edge){v,u,hd[v],0,-w};
	hd[v]=e_num;
}
void spfa()
{
	static int q[N*N];
	memset(h,0x7f,sizeof(h));
	h[q[l=r=1]=0]=0;
	while(l<=r)
	{
		for(int i=hd[q[l]];i;i=e[i].nxt)
		{
			if(e[i].f&&h[e[i].v]>h[q[l]]+e[i].w)
			{
				h[e[i].v]=h[q[l]]+e[i].w;
				if(!v[e[i].v])
					v[q[++r]=e[i].v]=1;
			}
		}
		v[q[l++]]=0;
	}
}
int dijkstra()
{
	memset(d,0x7f,sizeof(d));
	memset(v,0,sizeof(v));
	d[0]=0;
	q.push((node){0,0});
	while(!q.empty())
	{
		int k=q.top().v;
		q.pop();
		if(v[k])
			continue;
		v[k]=1;
		for(int i=hd[k];i;i=e[i].nxt)
		{
			if(e[i].f&&d[e[i].v]>d[k]+e[i].w+h[k]-h[e[i].v])
			{
				d[e[i].v]=d[k]+e[i].w+h[k]-h[e[i].v];
				p[e[i].v]=i;
				q.push((node){e[i].v,d[e[i].v]});
			}
		}
	}
	return v[T];
}
signed main()
{
	scanf("%d%d",&m,&n);
	T=n+n*m+1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",t[i]+j);
	for(int i=1;i<=n;i++)
	{
		add_edge(0,i,1,0);
		for(int j=1;j<=m;j++)
			for(int k=1;k<=n;k++)
				add_edge(i,n+(j-1)*n+k,1,k*t[i][j]);
	}
	for(int i=1;i<=n*m;i++)
		add_edge(n+i,T,1,0);
	spfa();
	int s=0;
	while(dijkstra())
	{
		for(int i=0;i<=T;i++)
			h[i]+=d[i];
		int mnf=1000000000;
		for(int i=T;i;i=e[p[i]].u)
			mnf=min(mnf,e[p[i]].f);
		for(int i=T;i;i=e[p[i]].u)
			e[p[i]].f-=mnf,e[p[i]^1].f+=mnf;
		s+=mnf;
		ans+=mnf*h[T]; 
	}
	printf("%.2lf",1.0*ans/n);
}