BZOJ 1070 修车【费用流】

2022-06-03 10:17:04

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

HINT

数据范围: (2<=M<=9,1<=N<=60), (1<=T<=1000)

题解

这道题需要我们将顾客与工人匹配，容易想到费用流

我们源点S从顾客流入，通过一条路径到达T，使这条路径上累加的费用就是总的等待时间。

问题是我们怎么构图。

我们想，不让工人去找顾客，让顾客去找工人，对于同一个工人，如果他总共要给x个顾客修车，那么对于第一个顾客，就有x个人要等，没错吧。第二个顾客就有x - 1个人要等

由这样的思想，我们拆工人，拆成m * n个，每个表示倒数第i次修车的工人，让每个顾客朝他们连边，权值为i * T，i表示这是倒数第i次，要有i个人等

所有边的流量都是1，剩余边的费用为0

跑一遍费用流就出来了

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

#include<algorithm>

#define LL long long int

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define fo(i,x,y) for (int i = (x); i <= (y); i++)

#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)

using namespace std;

const int maxn = 1005,maxm = 1000005,INF = 0x3f3f3f3f;

inline LL read(){

	LL out = 0,flag = 1;char c = getchar();

	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57) {out = out * 10 + c - 48; c = getchar();}

	return out * flag;

}

LL m,n;

int head[maxn],nedge = 0;

struct EDGE{

	LL from,to,f,w,next;

}edge[maxm];

inline void build(int u,int v,LL f,LL w){

	edge[nedge] = (EDGE) {u,v,f,w,head[u]};

	head[u] = nedge++;

	edge[nedge] = (EDGE) {v,u,0,-w,head[v]};

	head[v] = nedge++;

}

LL pre[maxn],d[maxn],S,T;

bool inq[maxn];

LL cost = 0;

inline void maxflow(){

	cost = 0;

	while (true){

		fill(d,d + maxn,INF);

		d[S] = 0; pre[S] = 0;

		queue<int> q;

		q.push(S);

		int u,to;

		while (!q.empty()){

			u = q.front();

			q.pop();

			inq[u] = false;

			Redge(u) {

				if (edge[k].f && d[to = edge[k].to] > d[u] + edge[k].w){

					d[to] = d[u] + edge[k].w;

					pre[to] = k;

					if (!inq[to]){

						q.push(to);

						inq[to] = true;

					}

				}

			}

		}

		if (d[T] == INF) break;

		LL flow = INF; u = T;

		while (u != S) {flow = min(flow,edge[pre[u]].f); u = edge[pre[u]].from;}

		cost += flow * d[T];

		u = T;

		while (u != S){

			edge[pre[u]].f -= flow;

			edge[pre[u] ^ 1].f += flow;

			u = edge[pre[u]].from;

		}

	}

}

int main()

{

	fill(head,head + maxn,-1);n = read();

	m = read();

	S = 0;

	T = 1001;

	LL t;

	for (int i = 1; i <= m; i++){

		build(i,T,1,0);

		for (int j = 1; j <= n; j++){

			t = read();

			for (int k = 1; k <= m; k++)

				build(j * m + k,i,1,k * t);

		}

	}

	for (int i = 1; i <= n; i++)

		for (int k = 1; k <= m; k++)

			build(S,i * m + k,1,0);

	maxflow();

	printf("%.2lf\n",(double) cost / m);

	return 0;

}

码农公寓