P7100 [w3R1] 团

SDqwq · 2020-11-23 23:33:17 · 题解

博客食用更佳

前置芝士：最短路

Step 0 题意

• 一张 n 个结点的无向带权图。

• 有 k 个集合；第 i 个集合可以表示为 S_i=\{(T_1,W_1),(T_2,W_2),…,(T_{|S_i|},W_{|S_i|})\}。

• 对于任何两对 (T_i,W_i),(T_j,W_j) 在同一个集合里面，图中会形成一条连 T_i 和 T_j 的边，边权为 W_i+W_j。

Step 1 暴力

按照题意暴力建图，直接跑堆优化 dijkstra 即可。

时间复杂度：\mathcal{O}((n+\sum|{S_i}^2|)\log \sum|{S_i}^2|)

Step 2 正解

观察暴力解法后发现主要问题是边数太大。

• 考虑在每个集合 S_i 中加入一个虚点 x。

执行完上述操作后可以发现仍然满足题目中 <T_i,T_j>=W_i+W_j(i,j\in[1,|S_i|]) 的要求。

此时边数为 2\times\sum|S_i|，可以承受。

时间复杂度：\mathcal{O}((n+\sum|S_i|)\log\sum|S_i|)

Step 3 代码

#include <cstdio>
#include <iostream>
#include <queue>

using namespace std;

typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3f;

int n, k, S, cnt, tot, T[400005], elast[600005];
ll W[400005], dis[600005];
bool vis[600005];

struct edge {
    int to, next;
    ll len;
} e[800005];

void add (int u, int v, ll w) {
    e[++cnt].to = v;
    e[cnt].len = w;
    e[cnt].next = elast[u];
    elast[u] = cnt;
}

struct node {
    ll dis;
    int id;
    node (ll _dis, int _id) {
        dis = _dis;
        id = _id;
    }
};

bool operator < (node x, node y) {
    return x.dis > y.dis;
}

priority_queue<node> pq;

void dijkstra (int x) {
    for (int i = 1; i <= tot; i++)
        dis[i] = inf;
    dis[x] = 0;
    pq.push(node(0, x));
    while (!pq.empty()) {
        node u = pq.top();
        pq.pop();
        if (vis[u.id])
            continue;
        vis[u.id] = true;
        for (int i = elast[u.id]; i != 0; i = e[i].next)
            if (dis[e[i].to] > dis[u.id] + e[i].len) {
                dis[e[i].to] = dis[u.id] + e[i].len;
                pq.push(node(dis[e[i].to], e[i].to));
            }
    }
}

int main () {
    scanf("%d %d", &n, &k);
    tot = n;
    for (int i = 1; i <= k; i++) {
        scanf("%d", &S);
        tot++;
        for (int j = 1; j <= S; j++) {
            scanf("%d %lld", &T[j], &W[j]);
            add(T[j], tot, W[j]);
            add(tot, T[j], W[j]);
        }
    }
    dijkstra(1);
    for (int i = 1; i <= n; i++)
        printf("%lld ", dis[i]);
    return 0;
}