F - Migration

题意

$N$ 頂点の木が与えられます。頂点には $1,\ldots,N$ の番号がついており、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ をつないでいます。また、頂点 $i$ には整数 $h_i$ が書かれています。

駒が $K$ 個あり、$i$ 番目の駒ははじめ頂点 $s_i$ に置かれています。あなたはこれから「一つ駒を選び、それが現在置かれている頂点に隣接するいずれかの頂点に移動させる」という操作を繰り返します。各駒 $i$ が頂点 $t_i$ に置かれている状態になったら操作を終了します。各駒 $i$ を頂点 $s_i$ から頂点 $t_i$ へ最短経路で移動させる必要は ありません。

ある駒の配置に対して、それぞれの駒が置かれている頂点に書かれた整数を足し合わせた値を ポテンシャル と呼ぶことにします。ただし、同じ頂点に複数の駒がある場合、その頂点の整数はその駒の個数だけ足し合わせるものとします。

操作を通してのポテンシャルの最大値は最小でいくつになるか求めてください。ただし、はじめの状態と終わりの状態も考えるものとします。

解析

考虑二分答案。现在我们只需实现判定一个固定的最大ポテンシャル是否可行。

设 $S=\{s_i\},T=\{t_i\}$ 分别表示所有駒的初始状态。若 $S$ 在固定的最大ポテンシャル可以到达 $T$，由于移动是双向的，则 $T$ 也可以到达 $S$，并且 $S$ 和 $T$ 能到达的状态的集合是相等的。我们要从该集合中选取一个有代表性的状态，借 $S$ 和 $T$ 是否都能到达该状态来判断 $S$ 和 $T$ 是否能互相到达。

这个状态就是，所有駒都处于可能到达的 $h_i$ 最小的节点的状态。将 $S$ 不断重复以下操作，直到无法操作为止：

• 选定一个駒进行移动，满足该駒移动后的节点的 $h_i$ 比移动前的节点的 $h_i$ 小，且过程中ポテンシャル不超出限制

最终得到的状态就是 $S$ 中所有駒都处于可能到达的 $h_i$ 最小的节点的状态 (这个状态是良定义的，因为一个駒处于更小的 $h_i$ 的节点时，其他的駒也会更容易到达更小的 $h_i$ 的节点)。因为在操作中，ポテンシャル总是在减小，每个駒能够到达的位置的集合总是在变大；在最终状态下，所有駒能够到达的位置的集合都被最大化，且都处于各自能到达的 $h_i$ 最小的节点。

于是我们对 $S$ 和 $T$ 分别不断操作，判断从它们得到的状态是否相等。实现时可以去掉二分，做到 $O(N^2+NK\log K)$ 的复杂度。

实现

#include <bits/stdc++.h>

typedef long long int ll;
const int maxn = 2e3 + 19;

struct Edge{
    int to, next;
}edge[maxn << 1];

int head[maxn];

inline void add(int from, int to){
    edge[++head[0]] = (Edge){to, head[from]};
    head[from] = head[0];
}

int n, k, h[maxn], s[2][maxn], same;
ll ans, res[2];
bool vist[maxn];

inline bool cmp(const int &a, const int &b){
    return h[a] < h[b] || (h[a] == h[b] && a < b);
}

int next[maxn], max[maxn];
void dfs(int node, int f, int s){
    static int dist[maxn];
    dist[node] = std::max(dist[f], h[node]);
    if(cmp(node, s)){
        if(!next[s]) next[s] = node, max[s] = dist[node];
        if(dist[node] < dist[next[s]] || (dist[node] == dist[next[s]] && cmp(node, next[s])))
            next[s] = node, max[s] = dist[node];
    }
    for(int i = head[node]; i; i = edge[i].next)
        if(edge[i].to != f)
            dfs(edge[i].to, node, s);
}

std::priority_queue<std::pair<ll, int>, std::vector<std::pair<ll, int> >, std::greater<std::pair<ll, int> > > q[2];

int main(){
    std::scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        std::scanf("%d", h + i);
    for(int i = 2, u, v; i <= n; ++i){
        std::scanf("%d%d", &u, &v);
        add(u, v), add(v, u);
    }
    for(int i = 1; i <= n; ++i)
        max[i] = 2e9, dfs(i, 0, i);
    std::scanf("%d", &k);
    for(int i = 1; i <= k; ++i)
        for(int j = 0; j < 2; ++j){
            std::scanf("%d", &s[j][i]);
            res[j] += h[s[j][i]];
        }
    ans = std::max(res[0], res[1]);
    for(int i = 1; i <= k; ++i){
        for(int j = 0; j < 2; ++j)
            if(next[s[j][i]])
                q[j].emplace(max[s[j][i]] - h[s[j][i]], i);
        if(!vist[i] && s[0][i] == s[1][i])
            vist[i] = true, ++same;
    }
    while(!q[0].empty() || !q[1].empty()){
        if(same == k) break;
        int j;
        if(q[1].empty() || (!q[0].empty() && res[0] + q[0].top().first <= res[1] + q[1].top().first)) j = 0;
        else j = 1;
        int i = q[j].top().second; ll d = q[j].top().first;
        q[j].pop();

        ans = std::max(ans, res[j] + d);
        res[j] -= h[s[j][i]];
        s[j][i] = next[s[j][i]];
        res[j] += h[s[j][i]];
        if(!vist[i] && s[0][i] == s[1][i])
            vist[i] = true, ++same;
        if(next[s[j][i]])
            q[j].emplace(max[s[j][i]] - h[s[j][i]], i);
    }
    std::printf("%lld\n", ans);
}

来源

AtCoder Regular Contest 115 F - Migration

评论