CF 1253E Antenna Coverage

题目描述

http://codeforces.com/problemset/problem/1253/E

Solution

注意到最终答案的形式一定是若干线段的并

首先将每个线段的所有可能覆盖区间和价值都预处理出来，时间复杂度为 $O(nm)$

然后我们考虑对于 $(l,r,k)$ 的覆盖，从 $l$ 连向 $r+1$，边权为 $k$

然后跑从 $1$ 到 $m+1$ 的最短路，注意需要连上 $i$ 到 $i-1$ 边权为 $0$ 的边

时间复杂度 $O(nm\log {nm})$

#include <iostream>
#include <queue>
#define maxn 100010
#define maxm 81
#define INF 1000000000
using namespace std;

int n, m;

struct Edge {
    int to, next, w;
} e[maxn * 81]; int c1, head[maxn];
inline void add_edge(int u, int v, int w) {
    e[c1].to = v; e[c1].w = w;
    e[c1].next = head[u]; head[u] = c1++;
}

struct Queue {
    int k, v;

    friend bool operator < (const Queue &u, const Queue &v) { return u.v > v.v; } 
};

int s, t, dis[maxn]; bool vis[maxn];
int dijkstra() {
    fill(dis, dis + maxn, INF); dis[s] = 0; 
    priority_queue<Queue> Q; Q.push({ s, dis[s] });
    while (!Q.empty()) {
        int u = Q.top().k; Q.pop();
        if (vis[u]) continue; vis[u] = 1;
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                Q.push({ v, dis[v] });
            }
        }
    }
    return dis[t]; 
} 

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; s = 1; t = m + 1; 
    for (int i = 2; i <= m + 1; ++i) add_edge(i, i - 1, 0); 
    for (int i = 1; i <= n; ++i) {
        int x, y, l, r, v = 0; cin >> x >> y;
        l = max(1, x - y); r = min(x + y, m);
        while (l >= 1 || r <= m) {
            l = max(1, l); r = min(r, m); 
            add_edge(l, r + 1, v++);
            --l; ++r;
        }
    } cout << dijkstra() << "\n";
    return 0;
}