[费用流][BZOJ1070]修车

时间:2023-07-18 15:39:55

修车

题目描述

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

输入

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

输出

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

样例输入

2 2
3 2
1 4

样例输出

1.50

提示

2<=M<=9,1<=N<=60 , 1<=T<=1000

又是一题看题解过的题...费用流难哇qaqq

对于每一个修车♂师傅,拆成N个点表示修N辆车

把车和所有的修车师傅拆成的N * M个点连边,记A[i, j]为第i个师傅修倒数第j辆车,流量为1(每辆车只能被修♂一次),费用为time[i , j] * k

关于费用:因为第j辆车在倒数第k个被修因此对全局产生的费用为time[i, j] * k (通俗的来说就是后面的人要排队啦w

S连每辆车,费用为0流量为1,每个师傅拆成的点连T,费用为0流量为1。

然后跑一遍MCMF结果除以k就好啦owo

代码:

 #include<algorithm>
#include<cstdio>
#include<cstring> const int Maxv = , inf = 0x6ffffff, T = ;
int Next[Maxv], Head[Maxv], from[Maxv], tim[][], w[Maxv], v[Maxv], q[Maxv], d[Maxv], ans, cnt = , n, m;
bool inq[Maxv];
struct edge{
int from, to, next, c, v;
}e[]; int read(){
int x = , f = ;
char c = getchar();
while (c < '' || c > '') {
if (c == '-') {
f = -;
}
c = getchar();
}
while(c >= '' && c <= '') {
x = x * + c - '';
c = getchar();
}
return x * f;
} void Add(int u, int v, int w, int c) {
cnt++;
e[cnt].next = Head[u];
e[cnt].to = v;
e[cnt].from = u;
e[cnt].c = c;
e[cnt].v = w;
Head[u] = cnt;
} void Add_Edge(int u, int v, int w, int c) {
Add(u, v, w, c);
Add(v, u, , -c);
} bool spfa()
{
for (int i = ; i <= T; i++) {
d[i] = inf;
}
int t = , w = ;
d[] = ;
inq[] = true;
q[] = ;
while(t != w) {
int now = q[t];
t++;
if(t == T) {
t = ;
}
for (int i = Head[now]; i; i = e[i].next) {
if (e[i].v && d[e[i].to] > d[now] + e[i].c) {
d[e[i].to] = d[now] + e[i].c;
from[e[i].to] = i;
if (!inq[e[i].to]) {
inq[e[i].to] = true;
q[w++] = e[i].to;
if(w == T) {
w = ;
}
}
}
}
inq[now] = false;
}
if (d[T] == inf) {
return false;
}
return true;
} void mcf()
{
int x = inf;
for (int i = from[T]; i; i = from[e[i].from]) {
x = std::min(x, e[i].v);
}
for (int i = from[T]; i; i = from[e[i].from]) {
e[i].v -= x;
e[i ^ ].v += x;
ans += e[i].c * x;
}
} int main(){
n = read();
m = read();
for (int i = ; i <= m; i++) {
for (int j = ; j <= n; j++) {
tim[i][j] = read();
}
}
for (int i = ; i <= n * m; i++) {
Add_Edge(, i, , );
}
for (int i = n * m + ; i <= n * m + m; i++) {
Add_Edge(i, T, , );
}
for (int i = ; i <= n; i++) {
for (int j = ; j <= m; j++) {
for (int k = ; k <= m; k++) {
Add_Edge((i - ) * m + j, n * m + k, , tim[k][i] * j);
}
}
}
while (spfa()) {
mcf();
}
printf("%.2lf", (double)ans / m);
return ;
}