【APIO2013】道路费用(TOLL)

标签：tag   lag   getch   operator   出现   swa   gre   std   continue   

先求一下原图的最小生成树，把不在最小生成树里的边全部删掉。

Mr.Greedy 的边会替换掉若干最小生成树上的边。

一个暴力做法是，先 \(2 ^ k\) 枚举哪些边一定在最小生成树中，把他们加入最小生成树。然后从小到达枚举原图上的边。如果能加入就直接加入，否则就会出现一个环，那么这个环上所有 Mr.Greedy 的边权值都不能大于这条边。这样的复杂度是 \(O(2^kn)\)

考虑优化这个暴力。显然，有一些边是无论如何都会在最小生成树里的。将 Mr.Greedy 的 \(k\) 条边全部插入最小生成树中，然后加入原图的边。能在此时被加入的边，一定会存在于任何一棵最小生成树中。

那么就把这些边直接缩起来。我们得到的新图中就只有不超过 \(k+1\) 个点，\(\binom{k+1}{2}\) 条边。

在新图上跑原来的暴力。现在我们只需考虑 \(O(k^2)\) 条原图的边对 \(O(k)\) 条 Mr.Greedy 的边的限制。

如果直接将一条路径的值取 Min，单次复杂度是 \(O(k^3)\)。但是事实上，因为最小生成树从小到大加边，一条边最先被赋值的时候就应该被赋到了最小值，所以可以对每个点再维护第一个没有被赋值的祖先边。总复杂度就可以做到 \(O(mlogm + 2^kk^2)\)

代码写的有点丑。

#pragma GCC optimize("2,Ofast,inline")
#include
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair
using namespace std;
const int N = 3e5 + 100;
const int inf = 0x3f3f3f3f;

template  T read(T &x) {
    int f = 0;
    register char c = getchar();
    while (c > '9' || c = '0' && c  V, G[N];

struct UFS {
    int top, u[N], v[N];
    int fa[N];
    LL siz[N];

    void init() {
        top = 0;
        for (int i = 1; i > i & 1) {
            int x = gdy[i + 1].a, y = gdy[i + 1].b;
            if (ufs.find(x) == ufs.find(y)) flag = 0;
            else {
                ufs.merge(x, y);
                G[x].pb(y);
                G[y].pb(x);
            }
        }
    }
    if (!flag) {
        while (ufs.top > now) {
            ufs.cancle();
        }
        return 0;
    }
    for (int i = 1; i > i & 1) {
            int u = gdy[i + 1].a, v = gdy[i + 1].b;
            if (dep[u]  now) {
        ufs.cancle();
    }
    return ans;
}

int main() {
    read(n); read(m); read(k);
    for (int i = 1; i 

【APIO2013】道路费用(TOLL)

标签：tag   lag   getch   operator   出现   swa   gre   std   continue   

原文地址：https://www.cnblogs.com/Vexoben/p/11822271.html