「BZOJ 2259」新型计算机 - 最短路

发表于 更新于 分类于 ， 阅读次数： Disqus：

题意描述

HydroOJ 链接

Tim 正在摆弄着他设计的“计算机”，他认为这台计算机原理很独特，因此利用它可以解决许多难题。 但是，有一个难题他却解决不了，是这台计算机的输入问题。新型计算机的输入也很独特，假设输入序列中有一些数字（都是自然数——自然数包括 \(0\) ），计算机先读取第一个数字 \(s_1\) ，然后顺序向后读入 \(s_1\) 个数字。接着再读一个数字 \(s_2\) ，顺序向后读入 \(s_2\) 个数字……依此类推。不过只有计算机正好将输入序列中的数字读完，它才能正确处理数据，否则计算机就会进行自毁性操作！

Tim 现在有一串输入序列。但可能不是合法的，也就是可能会对计算机造成破坏。于是他想对序列中的每一个数字做一些更改，加上一个数或者减去一个数，当然，仍然保持其为自然数。使得更改后的序列为一个新型计算机可以接受的合法序列。

不过 Tim 还希望更改的总代价最小，所谓总代价，就是对序列中每一个数操作的参数的绝对值之和。

写一个程序：

  1. 从文件中读入原始的输入序列；
  2. 计算将输入序列改变为合法序列需要的最小代价；
  3. 向输出文件打印结果。

\(100\%\) 的数据满足：\(n < 1 \times 10^6 + 1\)

解题思路

显然这是图论问题。我们可以抽象成对于一个序列 \(\{a_n\}\)，可从 \(i\) 跳到 \(i + a_i + 1\)，要求跳到 \(n + 1\)。可以对 \(a_i\) 修改，代价为修改的绝对值，问最小代价。

我们可以连边 \(i \stackrel{0}{\longrightarrow} i + a_i + 1\)，即从 \(i\) 到 \(i + a_i + 1\) 的权值为 \(0\) 的边。对于修改，我们可以对于 \(\forall i \in (1, n]\)，连边 \(i \stackrel{1}{\longrightarrow} i + 1\)、\(i \stackrel{1}{\longrightarrow} i - 1\) 即可模拟修改过程。而对于修改超出 \(n\) 的，即 \(i + a_i + 1 > n\)，我们可以连边 \(i \stackrel{i + a_i - n}{\longrightarrow} n + 1\)。

最后求最短路即可，可以用堆优化的 Dijkstra。本题略卡常，加个快读快写可过。

代码演示

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
130
131
132
133
134
135
#include <cstdio>
#include <climits>
#include <vector>
#include <queue>

const int MAXN = 1e6;

struct Node {
    std::vector<struct Edge> e;
    int d;
    bool v;
} N[MAXN + 2];

struct Edge {
    int s, t;
    int w;

    Edge(int s, int t, int w) : s(s), t(t), w(w) {}
};

int n;

inline void addEdge(int s, int t, int w) {
    N[s].e.push_back(Edge(s, t, w));
}

inline int dijkstra(const int s, const int t) {
    for (int i = 0; i <= n + 1; i++) N[i].d = INT_MAX;

    static std::priority_queue< std::pair<int, int>, std::vector< std::pair<int, int> >, std::greater< std::pair<int, int> > > q;
    N[s].d = 0;
    q.push(std::make_pair(0, s));

    while (!q.empty()) {
        std::pair<int, int> p = q.top();
        q.pop();

        int v = p.second;
        if (N[v].v) continue;
        N[v].v = true;

        for (Edge &e : N[v].e) {
            if (N[e.t].d > N[v].d + e.w) {
                N[e.t].d = N[v].d + e.w;
                q.push(std::make_pair(N[e.t].d, e.t));
            }
        }
    }

    return N[t].d;
}

struct IO {
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
    char buf[MAXSIZE], *p1, *p2;
    char pbuf[MAXSIZE], *pp;
    IO() : p1(buf), p2(buf), pp(pbuf) {}

    ~IO() { fwrite(pbuf, 1, pp - pbuf, stdout); }
    inline char gc() {
        if (p1 == p2) p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin);
        return p1 == p2 ? ' ' : *p1++;
    }

    inline bool blank(char ch) {
        return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
    }

    template <class T>
    inline void read(T &x) {
        double tmp = 1;
        bool sign = 0;
        x = 0;
        char ch = gc();
        for (; !isdigit(ch); ch = gc())
            if (ch == '-') sign = 1;
        for (; isdigit(ch); ch = gc()) x = x * 10 + (ch - '0');
        if (ch == '.')
            for (ch = gc(); isdigit(ch); ch = gc())
                tmp /= 10.0, x += tmp * (ch - '0');
        if (sign) x = -x;
    }

    inline void read(char *s) {
        char ch = gc();
        for (; blank(ch); ch = gc()) continue;
        for (; !blank(ch); ch = gc()) *s++ = ch;
        *s = 0;
    }

    inline void read(char &c) {
        for (c = gc(); blank(c); c = gc()) continue;
    }

    inline void push(const char &c) {
        if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
        *pp++ = c;
    }

    template <class T>
    inline void write(T x) {
        if (x < 0) x = -x, push('-');
        static T sta[35];
        T top = 0;
        do {
            sta[top++] = x % 10, x /= 10;
        } while (x);
        while (top) push(sta[--top] + '0');
    }

    template <class T>
    inline void write(T x, char lastChar) {
        write(x), push(lastChar);
    }
} io;

int main() {
    io.read(n);

    for (int i = 1; i <= n; i++) {
        int a;
        io.read(a);
        if (i + a <= n) addEdge(i, i + a + 1, 0);
        else addEdge(i, n + 1, i + a - n);
        if (i > 1) {
            addEdge(i, i + 1, 1);
            addEdge(i, i - 1, 1);
        }
    }

    io.write(dijkstra(1, n + 1), '\n');

    return 0;
}