洛谷P2053 [SCOI2007] 修车题解

题目链接：P2053 [SCOI2007] 修车

题意：

同一时刻有 \(N\) 位车主带着他们的爱车来到了汽车维修中心。

维修中心共有 \(M\) 位技术人员，不同的技术人员对不同的车进行维修所用的时间是不同的。

现在需要安排这 \(M\) 位技术人员所维修的车及顺序，使得顾客平均等待的时间最小。

说明：顾客的等待时间是指从他把车送至维修中心到维修完毕所用的时间。

输入格式：

第一行有两个数 \(M,N\)，表示技术人员数与顾客数。

接下来 \(N\) 行，每行 \(M\) 个整数。第 \(i+1\) 行第 \(j\) 个数表示第 \(j\) 位技术人员维修第 \(i\) 辆车需要用的时间 \(T_{i,j}\)。

输出格式：

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

数据范围：

\(2\le M\le 9\)，\(1\le N\le 60\)，\(1\le T\le 10^3\)。

考虑一个工人修 \(k\) 辆车的花费。假设这 \(k\) 辆车的花费为序列 \(T\) ，则 \[ \mathrm{ans} = \sum_{i = 1} ^ k T_i(k - i + 1) \] 对于倒数第 \(i\) 辆车，它的贡献为 \(i \times T_i\) （这里的 \(T_i\) 也是倒着数的）

于是我们可以把每个工人拆成 \(n\) 个点，分别表示修倒数第几辆车的自己。

时间复杂度 \(\mathcal{O}(m^2n^2)\)。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e3 + 15))

struct Edge { int v,w,c,rev; };
struct node { int u,i,j; } pre[N];
char vis[N]; queue<int> q;
vector<Edge> vec[N];
int n,m,s,t,tot,flow,cost,in[N],d[N];
bool spfa()
{
    memset(d, 0x3f, (tot + 5) * sizeof(int));
    memset(in, 0x3f, (tot + 5) * sizeof(int));
    memset(vis, 0, (tot + 5) * sizeof(char));
    q.push(s); vis[s] = 1; d[s] = 0; pre[t].u = 0;
    for(int u,v,w,c,j; !q.empty(); )
    {
        u = q.front(); q.pop(); vis[u] = 0;
        for(int i = 0; i < vec[u].size(); i++)
        {
            auto &e = vec[u][i]; tie(v,w,c,j) = tie(e.v,e.w,e.c,e.rev);
            if(w > 0 && d[v] > d[u] + c)
            {
                d[v] = d[u] + c; pre[v] = {u,i,j};
                down(in[v] = in[u], w); if(!vis[v]) { q.push(v); vis[v] = 1; }
            }
        }
    }
    return pre[t].u != 0;
}
void Dinic()
{
    while(spfa())
    {
        flow += in[t]; cost += in[t] * d[t];
        for(int u,i,j,v = t; v != s; v = pre[v].u)
        {
            u = pre[v].u, i = pre[v].i, j = pre[v].j;
            vec[u][i].w -= in[t]; vec[v][j].w += in[t];
        }
    }
}
void addEdge(int u,int v,int w,int c)
{
    vec[u].push_back({v, w, c, (int)(vec[v].size())});
    vec[v].push_back({u, 0, -c, (int)(vec[u].size() - 1)});
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cout << fixed << setprecision(2);
    cin >> m >> n; s = n + n * m + 1; t = tot = s + 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1,x; j <= m; j++)
        {
            cin >> x;
            for(int k = 1; k <= n; k++) addEdge(i, j * n + k, 1, x * k);
        }
    for(int i = 1; i <= n; i++) addEdge(s, i, 1, 0);
    for(int i = 1; i <= n * m; i++) addEdge(i + n, t, 1, 0);
    Dinic(); cout << ((double)cost / n) << '\n';
    return 0;
}