[SCOI2007] 修车

[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);
}