# bzoj 1070 [SCOI2007]修车

### Description

同一时刻有N位车主带着他们的爱车来到了汽车维修中心。维修中心共有M位技术人员，不同的技术人员对不同

### Input

第一行有两个m,n，表示技术人员数与顾客数。 接下来n行，每行m个整数。第i+1行第j个数表示第j位技术人

### Output

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

2 2

3 2

1 4

1.50

### 题解

S向每个人连容量为1、边权为0的边，对于第i个人，向(j,k)连容量为1、边权tim[j][i]*k的边，最小费用最大流即为答案。

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define N 40010
#define inf 0x33333333
using namespace std;
typedef pair<int, int> Pair;
struct MFMC {
struct node {
int from, to, next, flow, cost;
}e[N * 10];
int tot, st[N], pe[N], pv[N], dis[N], vis[N];
void init() {
tot = -1, memset(e, -1, sizeof e);
memset(st, -1, sizeof st);
}
void add(int x, int y, int z, int zz) {
e[++tot].to = y, e[tot].from = x;
e[tot].flow = z, e[tot].cost = zz;
e[tot].next = st[x], st[x] = tot;
}
void add_edge(int x, int y, int z, int zz) {
}
queue <int> que;
bool spfa(int S, int T) {
memset(dis, 0x33, sizeof dis);
memset(vis, 0, sizeof vis);
que.push(S), vis[S] = 1, dis[S] = 0;
while(!que.empty()) {
int now = que.front();
que.pop();
vis[now] = 0;
for (int i = st[now]; ~i; i = e[i].next)
if (e[i].flow > 0 && dis[e[i].to] > dis[now] + e[i].cost) {
dis[e[i].to] = dis[now] + e[i].cost;
pe[e[i].to] = i, pv[e[i].to] = now;
if (!vis[e[i].to])
vis[e[i].to] = 1, que.push(e[i].to);
}
}
return dis[T] < inf;
}
Pair mfmc(int S, int T) {
int COST = 0, FLOW = 0, flow;
while(spfa(S, T)) {
flow = inf;
for (int i = T; i != S; i = pv[i])
flow = min(flow, e[pe[i]].flow);
COST += flow * dis[T];
FLOW += flow;
for (int i = T; i != S; i = pv[i])
e[pe[i]].flow -= flow, e[pe[i] ^ 1].flow += flow;
}
return make_pair(FLOW, COST);
}
}mcmf;
int n, m, time[100][100];
main() {
scanf("%d%d", &m, &n);
mcmf.init();
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
scanf("%d", &time[i][j]);
int S = n * m + n + 1, T = S + 1;
for (int i = 1; i <= n; ++i)
mcmf.add_edge(S, n * m + i, 1, 0);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
for (int k = 1; k <= n; ++k)
mcmf.add_edge(n * m + i, (j - 1) * n + k, 1, time[i][j] * k);
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
mcmf.add_edge((j - 1) * n + i, T, 1, 0);
Pair ans = mcmf.mfmc(S, T);
printf("%.2lf\n", (double)ans.second/(double)n);
}