bzoj 1003

[ZJOI2006]物流运输

题解

设 $f[i][j]$ 表示从第 $i$ 天到第 $j$ 天这连续的几天内，从起点 $1$ 到终点 $m$ 的每日最小花费，也即是除去这几天内不可用的节点后，剩下的图中 $1$ 到 $m$ 的最短路.

设 $dp[i]$ 为考虑前 $i$ 天的最小总成本，则

$dp[i] = \min\left\{f[1][i] \cdot i, \min_{0 < j < i}\{dp[j] + f[j+1][i] \cdot(i-j) + K\}\right\}$

在求最短路时，用 $b[u][i]$ 表示结点 $u$ 在第 $i$ 天是否损坏，然后求出 $b[u]$ 的前缀和 $sb[u]$ ，那么结点 $u$ 在区间 $[l,r]$ 内一直可用当且仅当

$sb[u][r] = sb[u][l-1]$

可以在 $\mathcal{O}(1)$ 的时间内判断某个节点是否可用.

总复杂度 $\mathcal{O}(n^2(m+e\log{e}))$ .

代码

#include <cstdio>
#include <vector>
#include <bitset>
#include <utility>
#include <cstring>
#include <queue>

using namespace std;
typedef long long int ll;
#define pb push_back
typedef pair<int,int> pii;
#define mp make_pair
#define fi first
#define se second

#define MAXN (1 << 7)
#define MAXV (1 << 5)

int n, m, K;
vector<pii> g[MAXV];
int broken[MAXV][MAXN];

bool is_available(int u, int l, int r)
{
    return (broken[u][r] == broken[u][l - 1]);
}
priority_queue< pii, vector<pii>, greater<pii> > q;
int d[MAXV];
bitset<MAXV> solid;
int sp(int l, int r)
{
    while (!q.empty()) q.pop();
    memset(d, 0x3f, sizeof d);
    solid.reset();
    q.push(mp(d[1] = 0, 1));
    while (!q.empty())
    {
        int u = q.top().se; q.pop();
        if (solid.test(u)) continue;
        solid.set(u);
        if (u == m) break;
        for (vector<pii>::iterator it = g[u].begin(); it != g[u].end(); it++)
        {
            pii e = *it;
            int v = e.fi, w = e.se;
            if (!is_available(v, l, r)) continue;
            if (d[u] + w < d[v])
                q.push(mp(d[v] = d[u] + w, v));
        }
    }
    return d[m];
}

ll f[MAXN][MAXN], dp[MAXN];

int main(void)
{
    int i, j, e;
    scanf("%d%d%d%d", &n, &m, &K, &e);
    while (e--)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].pb(mp(v, w));
        g[v].pb(mp(u, w));
    }
    scanf("%d", &i);
    while (i--)
    {
        int P, a, b;
        scanf("%d%d%d", &P, &a, &b);
        for (e = a; e <= b; e++) broken[P][e] = 1;
    }
    for (i = 1; i <= n; i++)
    {
        for (e = 1; e <= m; e++)
            broken[e][i] += broken[e][i - 1];
    }
    for (i = 1; i <= n; i++)
        for (e = i; e <= n; e++)
            f[i][e] = sp(i, e);
    for (i = 1; i <= n; i++)
    {
        dp[i] = f[1][i] * i;
        for (j = 1; j < i; j++)
            if (f[j + 1][i] != 0x3f3f3f3f)
                dp[i] = min(dp[i], dp[j] + f[j + 1][i] * (i - j) + K);
    }
    printf("%lld\n", dp[n]);
    return 0;
}

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

(吐槽一下 bzoj 居然不能交 c++0x)

# bzoj 1003

# [ZJOI2006]物流运输

# 题解

# 代码

bzoj 1003

[ZJOI2006]物流运输

题解

代码