1070: [SCOI2007]修车

Description

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。现在需要安排这M位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。 说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

Input

第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人员维修第i辆车需要用的时间T。

Output

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

Sample Input

2 2

3 2

1 4

Sample Output

1.50

——我是愉快的分隔符——

本题一眼的费用流。

考虑每个工人，若工人修某辆车，则等待总时间是这个工人的修理时间*剩余车辆数。

所以可以将每辆车与源点连边，流量为1，费用为0，控制每辆车只被修一次。

每个工人拆成N个点，分别与汇点相连，流量为1，费用为0，控制工人在同一时间修理一次；

每辆车和每个工人对应的时间相连，流量为1，费用为车子的倒数数*修理时间。

一边费用流直接出。

下面是代码：

#include
        
         #include
         
          #include
          
           using namespace std;int m,n;int t[65][10];const int Maxm=100000;//最大边数 const int Maxn=1000;//最大点数 struct Edge{	Edge(){};	Edge(int a,int b,int c,int d,int e){		u=a;		v=b; 		f=c;		w=d;		nxt=e;	}	int u,v,f,w,nxt;//U当前点 V来自点 F最大流量 W费用 NXT下一个点 };int cnt=1;//边计数int inf=2147483647;//无限大 int g[Maxn+10];//点的边集的开始序号 Edge e[Maxm+10];//边集 int dist[Maxn+10];//费用 int src,sink;//源点与汇点 queue
           
             que;//宽搜队列 bool inque[Maxn+10];//宽搜判断标志 int from[Maxn+10];//来源->用于计算费用 int ans=0;//存储最小费用 inline int remin(int a,int b){	return a
            
             dist[now]+e[i].w){				dist[e[i].v]=dist[now]+e[i].w;				from[e[i].v]=i;				if (inque[e[i].v]==false){					inque[e[i].v]=true;					que.push(e[i].v);				}			}		}		inque[now]=false;	} 	if (dist[sink]==inf) return false;//无法在增广 	return true;}inline void calcAns(){	int minflow=inf;	for (int i=from[sink];i;i=from[e[i].u]) minflow=remin(minflow,e[i].f);//寻找整条路经的流量 	for (int i=from[sink];i;i=from[e[i].u]) {		e[i].f-=minflow;//正边减流量 		e[i^1].f+=minflow;//反边加流量 		ans+=e[i].w*minflow;//计算费用 	}}inline void minCostFlow(){	while(spfa())calcAns();}int main(){	 scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++)        for(int j=1;j<=n;j++)               scanf("%d",&t[i][j]);	src=0;//设置源点 	sink=1001;//设置汇点 	//建边 	for(int i=1;i<=n*m;i++)        addEdge(src,i,1,0);    for(int i=n*m+1;i<=n*m+m;i++)        addEdge(i,sink,1,0);    for(int i=1;i<=n;i++)       for(int j=1;j<=m;j++)          for(int k=1;k<=m;k++)             addEdge((i-1)*m+j,n*m+k,1,t[k][i]*j);	minCostFlow();	printf("%.2lf",(double)ans/m);	return 0;}