P2050 [NOI2012]美食节

发表于 | 阅读数

分配需要菜品给厨师，某个厨师做的第 $k$ 道菜，则他的等待时间就是这个厨师制作前$k$ 道菜的时间之和，求最小等待时间。

这是一道非常好的动态加点的费用流题目。

一开始的想法是考虑倒过来做菜，先考虑每个厨师菜的最小时间，然后做掉，接下来打上标记，即接下来做菜都是$\times 2$，依次递推即可。

显然不对$2,100$与$2,3$，但是如果厨师做一道菜又是最优的解决。

但是费用流，是有反向边的，如果这个不是最优，明显$s\rightarrow 100\rightarrow2\rightarrow 2\times 2$这样就可以保证最小了。

所以在$MCMF$基础上，每次增广动态加点。

边数的规模是 $\mathcal{O}(mp)$,点数$O(n+m+p)$ 的。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
#define INF 0x3f3f3f3f
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + c - '0', c = getchar();
    return x * f;
}
int p[N*100], ti[N][N];
int pos[N*100], d[N*100];
struct Edge
{
    int to, cap, nxt, f;
    Edge() {}
    Edge(int v, int c, int t, int k) : to(v), cap(c), nxt(t), f(k) {}
};
const int EN = 2e5 + 10;
const int EM = 5e6 + 10;
struct MCMF
{

    Edge e[EM << 1];
    int head[EN], scnt;
    int f[EN], dis[EN], vis[EN];
    pii pre[EN];
    MCMF() { scnt = 1; }
    void addEdge(int u, int v, int w, int k)
    {
        e[++scnt] = Edge(v, w, head[u], k);
        head[u] = scnt;
        e[++scnt] = Edge(u, 0, head[v], -k); ///!!!!
        head[v] = scnt;
    }
    bool spfa(int s, int t)
    {
        memset(vis, 0, sizeof(vis));
        memset(dis, INF, sizeof(dis));
        queue<int> q;
        dis[s] = 0;
        vis[s] = 1;
        f[s] = INF;
        q.push(s);
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            vis[x] = 0;
            for (int i = head[x]; i; i = e[i].nxt)
            {
                int to = e[i].to;

                if (dis[to] > dis[x] + e[i].f && e[i].cap)
                {
                    pre[to] = mk(x, i);
                    dis[to] = dis[x] + e[i].f;
                    f[to] = min(f[x], e[i].cap);
                    if (!vis[to])
                    {
                        vis[to] = 1;
                        q.push(to);
                    }
                }
            }
        }
        return dis[t] != INF;
    }
    pii Maxflow(int s, int t, int n, int m)
    {
        int flow = 0, res = 0;
        int cnt = n + m + 2;
        while (spfa(s, t))
        {

            for (int u = t; u != s; u = pre[u].first)
            {
                e[pre[u].second].cap -= f[t];
                e[pre[u].second ^ 1].cap += f[t];
                res += e[pre[u].second].f * f[t];
            }
            int u = pre[t].first;
            cnt++;
            d[pos[u]]++;
            for (int i = 1; i <= n; i++)
                addEdge(i, cnt, 1, (d[pos[u]] + 1) * ti[i][pos[u]]);
            pos[cnt] = pos[u];
            addEdge(cnt, t, 1, 0);
            flow += f[t];
        }
        return mk(flow, res);
    }
} mc;

int main()
{

    int n = read(), m = read();
    for (int i = 1; i <= n; i++)
        p[i] = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ti[i][j] = read();
    int s = n + m + 1, t = n + m + 2;
    for (int i = 1; i <= n; i++)
    {
        mc.addEdge(s, i, p[i], 0);
        for (int j = 1; j <= m; j++)
        {
            mc.addEdge(i, j + n, 1, ti[i][j]);
        }
    }
    for (int j = 1; j <= m; j++)
        mc.addEdge(j + n, t, 1, 0), pos[j + n] = j;
    printf("%d\n", mc.Maxflow(s, t, n, m).second);
}