DDOSvoid's Blog

bzoj 2238 Mst

发表于 分类于
本文字数： 3.7k 阅读时长 ≈ 3 分钟

题目描述

时间限制：20s 空间限制：256MB

题目描述

给出一个N个点M条边的无向带权图，以及Q个询问，每次询问在图中删掉一条边后图的最小生成树。(各询问间独立，每次询问不对之后的询问产生影响，即被删掉的边在下一条询问中依然存在)

输入格式

第一行两个正整数N,M(N<=50000,M<=100000)表示原图的顶点数和边数。

下面M行，每行三个整数X,Y,W描述了图的一条边(X,Y)，其边权为W（W<=10000）。保证两点之间至多只有一条边。

接着一行一个正整数Q，表示询问数。(1<=Q<=100000)

下面Q行，每行一个询问，询问中包含一个正整数T，表示把编号为T的边删掉(边从1到M按输入顺序编号)。

输出格式

Q行，对于每个询问输出对应最小生成树的边权和的值，如果图不连通则输出“Not connected”

样例输入

1
2
3
4
5
6
7
8
9
10
11
>4 4
>1 2 3 
>1 3 5 
>2 3 9 
>2 4 1 
>4 
>1 
>2 
>3 
>4

样例输出

1
2
3
4
5
6
7
8
9
10
11
12
>15 
>13 
>9 
>Not connected

>样例解释:
>无

>数据规模：
>10%的数据N,M,Q<=100。
>另外30%的数据，N<=1000
>100%的数据如题目。

提示

题目来源

没有写明来源

Solution

我们考虑如果删点以条树边的话，显然是找一条最小的能加入的边加入

我们考虑预处理答案，对于每条非树边，考虑将其加入后能替换掉哪些非树边

这个东西显然可以树剖维护，需要注意的是边转点只有有一点细节

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#define maxn 50010
#define maxm 100010
#define cE const Edge 
using namespace std;

int n, m, q;

int fa[maxn];
void init_fa() { for (int i = 1; i <= n; ++i) fa[i] = i; }

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

struct Edge {
    int fr, to, next, w, id; 
} e[maxn * 2], E[maxm]; int c1, head[maxn], Bl[maxm];
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++;
} 

bool use[maxm];

int sz[maxn], son[maxn], f[maxn], dep[maxn];
void dfs(int u, int fa) {
    sz[u] = 1; int Max = 0; 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        dep[v] = dep[u] + 1; f[v] = u; dfs(v, u); sz[u] += sz[v];
        if (sz[v] > Max) Max = sz[v], son[u] = v; 
    }
}

int top[maxn], id[maxn], c2, a[maxn];
void dfs(int u, int fa, int topf) {
    top[u] = topf; id[u] = ++c2;
    if (son[u]) dfs(son[u], u, topf);
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to, w = e[i].w;
        if (v == fa) continue; a[v] = w;
        if (v != son[u]) dfs(v, u, v); 
    } 
}

#define lc i << 1
#define rc i << 1 | 1
struct Seg {
    int v, tag;
} T[maxn * 4];
inline void Update(int i, int tag) { T[i].v = T[i].tag = tag; } 

inline void pushdown(int i) {
    int &tag = T[i].tag; if (!tag) return ;
    Update(lc, tag); Update(rc, tag);
    tag = 0;
} 

void update(int i, int l, int r, int L, int R, int v) {
    if (l > R || r < L) return ;
    if (L <= l && r <= R) return Update(i, v);
    int m = l + r >> 1; pushdown(i);
    update(lc, l, m, L, R, v); update(rc, m + 1, r, L, R, v);
}

int query(int i, int l, int r, int k) {
    if (l == r) return T[i].v;
    int m = l + r >> 1; pushdown(i);
    if (k <= m) return query(lc, l, m, k);
    else return query(rc, m + 1, r, k);
}

void update(int x, int y, int v) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        update(1, 1, n, id[top[x]], id[x], v);
        x = f[top[x]]; 
    }
    if (dep[x] > dep[y]) swap(x, y);
    update(1, 1, n, id[x] + 1, id[y], v); //注意边转成点之后一定要从 id[x] + 1 开始
} 

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

    cin >> n >> m; init_fa(); 
    for (int i = 1; i <= m; ++i) cin >> E[i].fr >> E[i].to >> E[i].w, E[i].id = i;
    sort(E + 1, E + m + 1, [](cE &u, cE &v) { return u.w < v.w; }); int k = 0; 
    for (int i = 1; i <= m; ++i) {
        int u = E[i].fr, v = E[i].to, w = E[i].w, fu, fv, id = E[i].id; Bl[id] = i; 
        if ((fu = find(u)) == (fv = find(v))) continue;
        mst += w; fa[fu] = fv; use[id] = 1; ++k;
        add_edge(u, v, id); add_edge(v, u, id); 
    } dep[1] = 1; dfs(1, 0); dfs(1, 0, 1); 
    for (int i = m; i; --i)
        if (!use[E[i].id]) update(E[i].fr, E[i].to, E[i].id);
    for (int i = 1; i <= n; ++i) ans[a[i]] = E[Bl[query(1, 1, n, id[i])]].w;
    cin >> q;
    if (k < n - 1) {
        for (int i = 1; i <= q; ++i) cout << "Not connected\n";
        return 0;
    }
    for (int i = 1; i <= q; ++i) {
        int x; cin >> x;
        if (!use[x]) cout << mst << "\n";
        else ans[x] ? cout << mst - E[Bl[x]].w + ans[x] << "\n" : cout << "Not connected\n";
    }
    return 0;
}