BZOJ1070【SCOI2007】修车 <费用流>

Problem

【SCOI2007】修车

$\mathrm{Time\;Limit:\;1\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

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\le M\le 9$, $1\le N\le 60$, $1\le T\le 1000$

标签：费用流

Solution

此题建模是费用流中常见的拆点建模。
把每个技术人员拆成$n$个点，第$k$个点代表着此工作人员修的倒数第$k$辆车对答案的贡献。
对于每个顾客，如果他倒数第$k$个修车，花费$t$的时间，会对答案产生$t\times k$的贡献。
因此从每个顾客向每个技术人员的$n$个点连边，容量为$1$，花费为$t\times k$，然后跑费用流即可。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX_N 10000
#define MAX_M 200000
#define INF 2147483647
using namespace std;
int n, m, s, t, ans, a[65][10];
int pre[MAX_N+5], cnt;
struct node {int v, c, w, nxt;} E[MAX_M+5];
void init() {s = 0, t = n*m+n+1, cnt = 0;    memset(pre, -1, sizeof(pre));}
void insert(int u, int v, int c, int w) {
    E[cnt].v = v, E[cnt].c = c, E[cnt].w = w, E[cnt].nxt = pre[u], pre[u] = cnt++;
    E[cnt].v = u, E[cnt].c = 0, E[cnt].w =-w, E[cnt].nxt = pre[v], pre[v] = cnt++;
}
bool SPFA() {
    queue <int> que;	bool inque[MAX_N+5];	int dis[MAX_N+5], pree[MAX_N+5];
    memset(inque, false, sizeof(inque)), memset(pree, -1, sizeof(pree));
    for (int i = s; i <= t; i++)	dis[i] = INF;
    dis[s] = 0, que.push(s), inque[s] = true;
    while (!que.empty()) {
        int u = que.front();	que.pop(), inque[u] = false;
        for (int i = pre[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && dis[u]+w < dis[v]) {
                dis[v] = dis[u]+w, pree[v] = i;
                if (!inque[v])	que.push(v), inque[v] = true;
            }
        }
    }
    if (dis[t] == INF)	return false;
    int flow = INF;
    for (int i = pree[t]; ~i; i = pree[E[i^1].v])	flow = min(flow, E[i].c);
    for (int i = pree[t]; ~i; i = pree[E[i^1].v])	E[i].c -= flow, E[i^1].c += flow;
    ans += dis[t];	return true;
}
int main() {
    scanf("%d%d", &m, &n), init();
    for (int i = 1; i <= n; i++)	for (int j = 1; j <= m; j++)	scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)	insert(s, i, 1, 0);
    for (int i = 1; i <= n; i++)	for (int j = 1; j <= m; j++)	for (int k = 1; k <= n; k++)	insert(i, j*n+k, 1, a[i][j]*k);
    for (int j = 1; j <= m; j++)	for (int k = 1; k <= n; k++)	insert(j*n+k, t, 1, 0);
    while (SPFA()) ;
    printf("%.2lf", (double)ans/n);
    return 0;
}