给定一个无向带权图,边权只有 A, B 两种,对于每个点 p \in [1, n] 求出 1 \rightarrow p 所有最小生成树中的最短距离。N \leq 70, M \leq 200

看完这题有个大胆的想法就是直接跑最短路,然而这连样例 1 都过不去,问题出在哪里呢?

不妨假设 A \leq B,考虑把所有边权为 A 的边连起来会使图形成一个个联通块。那么为了使得生成树最小,剩下的边权为 B 的边就需要起到将这些联通块连接起来的作用。

然而如果直接跑最短路,我们可以发现通过别的联通块再回到当前联通块(走两次 B 边)可能比一直在联通块里面走(一直走 A 边)的距离更短,所以我们需要将避免同一个联通块被经过两次。

然而如果我们直接状压记录联通块,显然会超时。但是可以发现会出现上述特殊情况的仅当这个联通块的大小大于等于四,所以我们可以只状压记录大小大于等于四的联通块,复杂度为 \mathcal(2^{\frac n4} \cdot n (n + m) \log (n+m)),可以通过本题。

代码:

// =================================
//   author: memset0
//   date: 2019.05.01 10:38:17
//   website: https://memset0.cn/
// =================================
#include <bits/stdc++.h>
#define ll long long
#define debug(...) ((void)0)
#ifndef debug
#define debug(...) fprintf(stderr,__VA_ARGS__)
#endif
namespace ringo {
template <class T> inline void read(T &x) {
    x = 0; register char c = getchar(); register bool f = 0;
    while (!isdigit(c)) f ^= c == '-', c = getchar();
    while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
    if (f) x = -x;
}
template <class T> inline void print(T x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar('0' + x % 10);
}
template <class T> inline void print(T x, char c) { print(x), putchar(c); }

const int N = 75, M = 1 << 17;
int col[N], id[N];
ll ans[N], dis[N][M];
bool tag[N], vis[N][M];
std::vector<int> node_set;
int n, m, id_cnt, col_cnt, key1, key2;

struct Map {
    std::vector<std::pair<int, int>> graph[N];
    inline void add_edge(int u, int v, int w) {
        graph[u].push_back(std::make_pair(v, w));
        graph[v].push_back(std::make_pair(u, w));
    }
} map0, map1, map2;

struct status {
    int u, s; ll w;
    inline bool operator < (const status &other) const {
        if (w != other.w) return w > other.w;
        if (u != other.u) return u > other.u;
        return s > other.s;
    }
};
std::priority_queue<status> q;

void dfs(int u) {
    tag[u] = 1;
    node_set.push_back(u);
    for (auto it : map1.graph[u]) {
        int v = it.first, w = it.second;
        if (!tag[v]) dfs(v);
    }
}

inline void push_status(int u, int s, ll w) {
    // printf("> %d %d %lld\n", u, s, w);
    if (w < dis[u][s]) {
        dis[u][s] = w;
        q.push((status){u, s, w});
    }
}

void main() {
    memset(ans, 0x3f, sizeof(ans));
    memset(dis, 0x3f, sizeof(dis));
    read(n), read(m), read(key1), read(key2);
    if (key1 > key2) std::swap(key1, key2);
    for (int u, v, w, i = 1; i <= m; i++) {
        read(u), read(v), read(w);
        map0.add_edge(u, v, w);
        if (w == key1) map1.add_edge(u, v, w);
        if (w == key2) map2.add_edge(u, v, w);
    }
    for (int i = 1; i <= n; i++) if (!tag[i]) {
        node_set.clear();
        dfs(i);
        ++col_cnt;
        for (auto u : node_set) {
            col[u] = col_cnt;
        }
        if (node_set.size() > 3) {
            id[col_cnt] = ++id_cnt;
        }
    }
    // for (int i = 1; i <= n; i++) print(col[i], " \n"[i == n]);
    // for (int i = 1; i <= n; i++) print(id[col[i]], " \n"[i == n]);
    push_status(1, id[1] ? 1 : 0, 0);
    while (q.size()) {
        int u = q.top().u, s = q.top().s;
        q.pop();
        if (vis[u][s]) continue;
        vis[u][s] = 1;
        for (auto it : map0.graph[u]) {
            int v = it.first, w = it.second;
            // printf("%d -> %d : %lld\n", u, v, w);
            if (col[u] == col[v] && w == key2) continue;
            if (id[col[v]] && id[col[u]] != id[col[v]]) {
                if (s & (1 << (id[col[v]] - 1)))
                    continue;
                push_status(v, s | (1 << (id[col[v]] - 1)), dis[u][s] + w);
            } else {
                push_status(v, s, dis[u][s] + w);
            }
        }
    }
    for (int x = 0; x < (1 << id_cnt); x++) {
        for (int i = 1; i <= n; i++)
            ans[i] = std::min(ans[i], dis[i][x]);
    }
    for (int i = 1; i <= n; i++) {
        print(ans[i], " \n"[i == n]);
    }
}

} signed main() {
#ifdef MEMSET0_LOCAL_ENVIRONMENT
    freopen("1.in", "r", stdin);
#endif
    return ringo::main(), 0;
}

none

洛谷5358 [SDOI2019]快速查询
上一篇 «
CF1149C Tree Generator™
» 下一篇