HNOI2010 城市建设

题目:

  PS国是一个拥有诸多城市的大国,国王Louis为城市的交通建设可谓绞尽脑汁。Louis可以在某些城市之间修建道路,在不同的城市之间修建道路需要不同的花费。Louis希望建造最少的道路使得国内所有的城市连通。但是由于某些因素,城市之间修建道路需要的花费会随着时间而改变,Louis会不断得到某道路的修建代价改变的消息,他希望每得到一条消息后能立即知道使城市连通的最小花费总和, Louis决定求助于你来完成这个任务。

思路:

  好神仙的分治题啊,现在还没想明白怎么想到分治上的
  假设你已经确定正解是分治,那么对于一个大小为 的分治区间,为了保证复杂度正确,对于这个区间的操作次数要是一个关于 的函数
  现在有一个 (为了方便有这样的点对表示点数和边数)的图。在当前的分治区间内,有 条边的权值因为被修改过不确定。
  先假设这些边的权值都为 ,构造一次 ,此时如果一条权值不为 的边被选中了,那它一定出现在最终答案中。因为这样的边有 (忽略常数)条,把这些边加入图中,再把联通块缩成一个点,这样点数就能被缩到 了。
  再假设这些边权值都为 ,这次不出现在 中的边就一定不出现在最终答案中,这样留下的边就只有 条,再加上权值不确定的边,就得到了一张 的图。
  每一层都这样收缩图,到 时就直接求 。一位每层的复杂度都是 ,所以总的复杂度就是

代码:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i##_END_(b); i <= i##_END_; i++)
#define drep(i, a, b) for(int i(a), i##_END_(b); i >= i##_END_; i--)
using namespace std;
typedef long long ll;
const int N = 20005, M = 50005, inf = 1e9;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}

struct Edge {
    int u, v, w, id;
    bool operator< (const Edge e) const {
        return w < e.w;
    }
} edge[20][M];

int ufs[N];
int find(int x) {
    if(x == ufs[x]) return x;
    return ufs[x] = find(ufs[x]);
}
bool merge(int u, int v) {
    u = find(u); v = find(v);
    if(u == v) return false;
    ufs[u] = v;
    return true;
}
void init(int x, Edge *e) {
    rep(i, 1, x) {
        ufs[e[i].u] = e[i].u;
        ufs[e[i].v] = e[i].v;
    }
}

int val[M], k[M], c[M], vec[M], id[M];
ll ans[M];
bool mark[M];
void cdq(int d, int l, int r, int en, ll now) {
    Edge *e = edge[d];
    if(l == r) {
        val[k[l]] = c[l];
        rep(i, 1, en) e[i].w = val[e[i].id];
        sort(e + 1, e + 1 + en);
        init(en, e);
        rep(i, 1, en) 
            if(merge(e[i].u, e[i].v))
                now += e[i].w;
        ans[l] = now;
        return;
    }
    Edge *p = edge[d + 1];
    int tot = 0;
    rep(i, 1, en) e[i].w = val[e[i].id];
    sort(e + 1, e + 1 + en);
    init(en, e);
    rep(i, l, r) mark[k[i]] = true;
    rep(i, 1, en) if(mark[e[i].id]) merge(e[i].u, e[i].v);
    rep(i, 1, en)
        if(merge(e[i].u, e[i].v)) 
            if(e[i].w != -inf) {
                vec[++tot] = i;
                now += e[i].w;
            }
    rep(i, 1, en) e[i].w = val[e[i].id];
    init(en, e);
    rep(i, 1, tot) merge(e[vec[i]].u, e[vec[i]].v);
    rep(i, 1, en) {
        id[e[i].u] = find(e[i].u);
        id[e[i].v] = find(e[i].v);
    }
    tot = 0;
    rep(i, 1, en) {
        int u = id[e[i].u], v = id[e[i].v];
        Edge nw = (Edge) {u, v, e[i].w, e[i].id};
        if(mark[e[i].id]) 
            p[++tot] = nw;
        else if(merge(e[i].u, e[i].v)) 
            p[++tot] = nw;
    }
    int mid = (l + r) >> 1;
    rep(i, l, r) mark[k[i]] = false;
    cdq(d + 1, l, mid, tot, now); 
    cdq(d + 1, mid + 1, r, tot, now);
}

int main() {
    // freopen("data.in", "r", stdin);
    int n, m, q;
    scanf("%d%d%d", &n, &m, &q);
    Edge *e = edge[0];
    rep(i, 1, m) {
        scanf("%d%d%d", &e[i].u, &e[i].v, &val[i]);
        e[i].id = i;
    }
    rep(i, 1, q) scanf("%d%d", &k[i], &c[i]);
    cdq(0, 1, q, m, 0);
    rep(i, 1, q) printf("%lld\n", ans[i]);
    return 0;
}