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

Data Range

对于所有的数据, 满足:\(2 \leq m \leq 9, 1 \leq n \leq 60, 1 \leq T \leq 1000\)

Explanation

这道题应该是一道很好做的费用流, 参考黄学长题解:

没写 cnt=1 调了半天、、、

\(n\) 辆车,\(m\) 个工人.

把每个工人拆成 \(n\) 个点. 记为 \(A[i, j]\) 表示第 \(i\) 个工人修倒数第 \(j\) 辆车.

每个车跟所有 \(nm\) 个工人拆出的点连边. 流量为 \(1\), 费用为 \(time[i, j] \times k\).

源和每辆车连边,\(nm\) 个点和汇连边, 流量都为 \(1\), 费用同为 \(0\).

为什么这么构图呢?

考虑第 \(i\) 个工人, 他修第 \(j\) 辆车只对后面要修的车有影响, 而前面修过的车已经对当前没有影响了.

而这个影响就是后面每个将要修理的车都多等待了 \(time\) 的时间.

其他边流量都为 \(1\) 是显然的, 每辆车修一次, 每个工人一个时段只能修理一辆车.

但是这道题调了差不多三个小时 [Facepalm]

为什么呢? 因为本人因为安全的因素, 通常都是保证做题时尽量用 long long 的, 然而这次 居然遇上了这样一道不会爆 long long 地题目, 然后加上 OJ 极其玄学, 所以:

调了三个小时, 将各种代码拷过来一行一行地等价代替, 然后发现一直 AC, 最后交完了发现和原来的代码差不多, 结果 diff 一下出来这样一个结果:

D:\Desktop>diff 1070.cpp 1070_wa.cpp
18c18
<         int u, v; int flow, cost;
---
>         int u, v; lli flow, cost;
23c23
<     int dist[maxn];
---
>     lli dist[maxn];
25c25
<     void add_edge(int u, int v, int flow, int cost)
---
>     void add_edge(int u, int v, lli flow, lli cost)
61c61
<     int eval()
---
>     lli eval()
63c63
<         int res = 0;
---
>         lli res = 0;
65c65
<             int tmp = infinit;
---
>             lli tmp = infinit;
100c100
<     int res = graph.eval();
---
>     lli res = graph.eval();

当时就懵了~ 为什么正解和错解就差这么一点......

上面就是各种叫人作呕的提交记录 (本来今天想写五六道题的结果都被迷之 hustoj 拖慢了) 我觉得 lavendir 有必要关注这一件事...... 这是继 (全局变量/局部变量) 之后本人遇到的第二次 bug......

顺便附上 TLE 的代码 (大家可以自己试一试)


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxN = 100, maxn = 1010, maxm = 100100;
const lli infinit = 0x0f3f3f3f;

class SpfaMaxFlowMinCost
{
public:
    struct edge
    {
        int u, v; lli flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], *from[maxn], epool[maxm];
    lli dist[maxn];
    bool inque[maxn];
    void add_edge(int u, int v, lli flow, lli cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = - cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool spfa(void)
    {
        for (int i = 0; i <= n; i++)
            dist[i] = infinit, inque[i] = false, from[i] = NULL;
        dist[s] = 0; inque[s] = true;
        queue<int> que;
        que.push(s);
        while (!que.empty())
        {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && dist[p] + ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        inque[ep->v] = true;
                        que.push(ep->v);
                    }
                }
            inque[p] = false;
        }
        if (dist[t] >= infinit)
            return false;
        return true;
    }
    lli eval()
    {
        lli res = 0;
        while (spfa()) {
            lli tmp = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                tmp = min(tmp, ep->flow);
            for (edge *ep = from[t]; ep; ep = from[ep->u]) {
                ep->flow -= tmp;
                ep->rev->flow += tmp;
                res += ep->cost * tmp;
            }
        }
        return res;
    }
} graph;

int n, m;
int arr[maxN][maxN];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &arr[i][j]);
    // Building graph.
    graph.s = 0;
    graph.t = 1001;
    graph.n = 1001;
    graph.ecnt = 1;
    for (int i = 1; i <= n * m; i++)
        graph.add_edge(graph.s, i, 1, 0);
    for (int i = n * m + 1; i <= n * m + m; i++)
        graph.add_edge(i, graph.t, 1, 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= m; k++)
                graph.add_edge((i - 1) * m + j, n * m + k, 1, arr[k][i] * j);
    lli res = graph.eval();
    printf("%.2Lf", (llf)res / m);
    return 0;
}

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <queue>

using namespace std;
typedef long long lli;
typedef long double llf;
const int maxN = 100, maxn = 1010, maxm = 100100;
const lli infinit = 0x0f3f3f3f;

class SpfaMaxFlowMinCost
{
public:
    struct edge
    {
        int u, v; int flow, cost;
        edge *next, *rev;
    };
    int n, s, t, ecnt;
    edge *edges[maxn], *from[maxn], epool[maxm];
    int dist[maxn];
    bool inque[maxn];
    void add_edge(int u, int v, int flow, int cost)
    {
        edge *p = &epool[++ecnt],
             *q = &epool[++ecnt];
        p->u = u; p->v = v; p->flow = flow; p->cost = cost;
        p->next = edges[u]; edges[u] = p; p->rev = q;
        q->u = v; q->v = u; q->flow = 0; q->cost = - cost;
        q->next = edges[v]; edges[v] = q; q->rev = p;
        return ;
    }
    bool spfa(void)
    {
        for (int i = 0; i <= n; i++)
            dist[i] = infinit, inque[i] = false, from[i] = NULL;
        dist[s] = 0; inque[s] = true;
        queue<int> que;
        que.push(s);
        while (!que.empty())
        {
            int p = que.front();
            que.pop();
            for (edge *ep = edges[p]; ep; ep = ep->next)
                if (ep->flow && dist[p] + ep->cost < dist[ep->v]) {
                    dist[ep->v] = dist[p] + ep->cost;
                    from[ep->v] = ep;
                    if (!inque[ep->v]) {
                        inque[ep->v] = true;
                        que.push(ep->v);
                    }
                }
            inque[p] = false;
        }
        if (dist[t] >= infinit)
            return false;
        return true;
    }
    int eval()
    {
        int res = 0;
        while (spfa()) {
            int tmp = infinit;
            for (edge *ep = from[t]; ep; ep = from[ep->u])
                tmp = min(tmp, ep->flow);
            for (edge *ep = from[t]; ep; ep = from[ep->u]) {
                ep->flow -= tmp;
                ep->rev->flow += tmp;
                res += ep->cost * tmp;
            }
        }
        return res;
    }
} graph;

int n, m;
int arr[maxN][maxN];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &arr[i][j]);
    // Building graph.
    graph.s = 0;
    graph.t = 1001;
    graph.n = 1001;
    graph.ecnt = 1;
    for (int i = 1; i <= n * m; i++)
        graph.add_edge(graph.s, i, 1, 0);
    for (int i = n * m + 1; i <= n * m + m; i++)
        graph.add_edge(i, graph.t, 1, 0);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 1; k <= m; k++)
                graph.add_edge((i - 1) * m + j, n * m + k, 1, arr[k][i] * j);
    int res = graph.eval();
    printf("%.2Lf", (llf)res / m);
    return 0;
}