P2495 [SDOI2011] 消耗战

[SDOI2011] 消耗战

题目描述

在一场战争中,战场由 n 个岛屿和 n-1 个桥梁组成,保证每两个岛屿间有且仅有一条路径可达。现在,我军已经侦查到敌军的总部在编号为 1 的岛屿,而且他们已经没有足够多的能源维系战斗,我军胜利在望。已知在其他 k 个岛屿上有丰富能源,为了防止敌军获取能源,我军的任务是炸毁一些桥梁,使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同,所以炸毁不同的桥梁有不同的代价,我军希望在满足目标的同时使得总代价最小。

侦查部门还发现,敌军有一台神秘机器。即使我军切断所有能源之后,他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁,而且会重新随机资源分布(但可以保证的是,资源不会分布到 1 号岛屿上)。不过侦查部门还发现了这台机器只能够使用 m 次,所以我们只需要把每次任务完成即可。

输入格式

第一行一个整数 n,表示岛屿数量。

接下来 n-1 行,每行三个整数 u,v,w ,表示 u 号岛屿和 v 号岛屿由一条代价为 w 的桥梁直接相连。

n+1 行,一个整数 m ,代表敌方机器能使用的次数。

接下来 m 行,第 i 行一个整数 k_i ,代表第 i 次后,有 k_i 个岛屿资源丰富。接下来 k_i 个整数 h_1,h_2,…, h_{k_i} ,表示资源丰富岛屿的编号。

输出格式

输出共 m 行,表示每次任务的最小代价。

样例 #1

样例输入 #1

10
1 5 13
1 9 6
2 1 19
2 4 8
2 3 91
5 6 8
7 5 4
7 8 31
10 7 9
3
2 10 6
4 5 7 8 3
3 9 4 6

样例输出 #1

12
32
22

提示

数据规模与约定

  • 对于 10\% 的数据,n\leq 10, m\leq 5
  • 对于 20\% 的数据,n\leq 100, m\leq 100, 1\leq k_i\leq 10
  • 对于 40\% 的数据,n\leq 1000, 1\leq k_i\leq 15
  • 对于 100\% 的数据,2\leq n \leq 2.5\times 10^5, 1\leq m\leq 5\times 10^5, \sum k_i \leq 5\times 10^5, 1\leq k_i< n, h_i\neq 1, 1\leq u,v\leq n, 1\leq w\leq 10^5

  • Code

#include<bits/stdc++.h>
constexpr int maxn = 250005, lim = 18, inf = 0x3f3f3f3f;
using namespace std;
using cint = const int&;
using ll = long long;
using cll = const ll&;
using edge = pair<int, ll>;
using key = pair<int, int>;
key keys[maxn];
vector<edge> tedge[maxn], vedge[maxn];
int n, m, u, v, w, k;
ll d[maxn];
bool imp[maxn];
int dfn[maxn], dfns, dep[maxn], fa[lim + 1][maxn], g[lim + 1][maxn];
#define unsigned
unsigned char lg[maxn];
void dfs(cint u, cint f, cll w) {
    dep[u] = dep[f] + 1;
    dfn[u] = ++dfns;
    fa[0][u] = f, g[0][u] = w;
    for (unsigned char i = 1; fa[i - 1][u]; ++i)
        fa[i][u] = fa[i - 1][fa[i - 1][u]],
        g[i][u] = min(g[i - 1][u], g[i - 1][fa[i - 1][u]]);
    for (const auto& [v, w] : tedge[u]) {
        if (v == f) continue;
        dfs(v, u, w);
    }
}

void dp(cint u) {
    for (const auto& [v, w] : vedge[u]) {
        dp(v);
        if (imp[v]) d[u] += w;
        else d[u] += min(w, d[v]);
        imp[v] = d[v] = 0;
    }
    vedge[u].clear();
}

inline int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    while (dep[u] > dep[v]) u = fa[lg[dep[u] - dep[v]]][u];
    if (u == v) return v;
    for (unsigned char i = lg[dep[u]]; i >= 0; --i)
        if (fa[i][u] != fa[i][v])
            u = fa[i][u], v = fa[i][v];
    return fa[0][u];
}

inline int getmindis(cint u, cint v) {
    int ans = inf;
    unsigned char len;
    for (int i = u; len = lg[dep[i] - dep[v]], dep[i] > dep[v]; i = fa[len][i])
        ans = min(ans, g[len][i]);
    return ans;
}

inline void addedge(cint u, cint v) {
    vedge[u].push_back({ v,getmindis(v,u) });
}
stack<int> s;
signed main() {
    s.push(1);
    memset(g, inf, sizeof(g));
    for (int i = 2; i < maxn; ++i) lg[i] = lg[i >> 1] + 1;
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i) {
        cin >> u >> v >> w;
        tedge[u].push_back({ v,w });
        tedge[v].push_back({ u,w });
    }
    dfs(1, 0, 0);
    cin >> m;
    while (m--) {
        cin >> k;
        for (int h, i = 1; i <= k; ++i) {
            cin >> h;
            imp[h] = 1;
            keys[i] = { dfn[h],h };
        }
        sort(keys + 1, keys + k + 1);
        for (int i = 1; i <= k; ++i) {
            int u = keys[i].second, l = lca(u, s.top());
            while (s.top() != l) {
                const int top1 = s.top();
                s.pop();
                int top2 = s.top();
                if (dfn[top2] < dfn[l]) s.push(top2 = l);
                addedge(top2, top1);
            }
            s.push(u);
        }
        while (s.top() != 1) {
            const int top1 = s.top();
            s.pop();
            addedge(s.top(), top1);
        }
        dp(1);
        cout << d[1] << '\n';
        d[1] = 0;
    }
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇