BZOJ2001: [Hnoi2010]City 城市建设
分治 MST 好题    2016-10-14 21:35:16    229    -1    0
jszyxw   分治 MST 好题

2001: [Hnoi2010]City 城市建设

Time Limit: 20 Sec  Memory Limit: 162 MB
Submit: 1094  Solved: 536
[Submit][Status][Discuss]

Description

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

Input

文件第一行包含三个整数N,M,Q,分别表示城市的数目,可以修建的道路个数,及收到的消息个数。 接下来M行,第i+1行有三个用空格隔开的整数Xi,Yi,Zi(1≤Xi,Yi≤n, 0≤Zi≤50000000),表示在城市Xi与城市Yi之间修建道路的代价为Zi。接下来Q行,每行包含两个数k,d,表示输入的第k个道路的修建代价修改为d(即将Zk修改为d)。

Output

输出包含Q行,第i行输出得知前i条消息后使城市连通的最小花费总和。

Sample Input

5 5 3
1 2 1
2 3 2
3 4 3
4 5 4
5 1 5
1 6
1 1
5 3

Sample Output

14
10
9

HINT

 

【数据规模】 对于20%的数据, n≤1000,m≤6000,Q≤6000。 有20%的数据,n≤1000,m≤50000,Q≤8000,修改后的代价不会比之前的代价低。 对于100%的数据, n≤20000,m≤50000,Q≤50000。

 

Solution

题意就是维护动态最小生成树。。

考虑分治,但是看起来并不满足分治的条件

我们想办法缩小点集和边集的大小。

对于q个询问里修改的边,我们设这个边集为Q,全集为E,那么对于E-Q中的边,做一遍MST,MST中的边集设为G,那么对于E-Q-G中的边,不论询问怎么改变,这些边都不会在MST中,所以我们可以删除这些边。

这样边集大小变成n - 1 + q,  点集大小仍为n

之后将Q中的边的边权都赋值为-INF,这时做一遍MST,如果E-Q的边在MST中,这时代表就算修改的边最小时这些边也要选,也就是这些边是保证MST连通性的必要的边,这些边我们也没有必要考虑,因为必须要选,所以将这条边连接的两个点合并成一个点。

边数和点数都减少n - q - 1,边集大小 = (n  + q - 1) - (n - q - 1) = 2 * q,点集大小 = n - (n - q - 1) = q + 1

这样规模就变成了O(q)的了,我们对询问分治,在分治的同时执行以上两个操作,再加上每次kruskal,总复杂度O(Qlog^2Q)

 

据说可以做到O(Q log Q)..

挖坑待填QAQ

 

/*{{{*/
#include <bits/stdc++.h>

#pragma GCC optimize("O2")
#define VAL(x) #x " = " << x << " "

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

string program_name = __FILE__;
string iput = program_name.substr(0, program_name.length() - 4) + ".in";
string oput = program_name.substr(0, program_name.length() - 4) + ".out";

template <class T> inline bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }
 
template <class T> inline T &read(T &x) 
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) if (c == '-') f = -1;
    for (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x *= f;
}
 
template <class T> void write(T x, char p = '\n') 
{
    register T tmp = 1;
    if (x < 0) putchar('-'), x = -x;
    while (x / tmp > 9) tmp *= 10;
    while (tmp) putchar(x / tmp + 48), x -= x / tmp * tmp, tmp /= 10;
    putchar(p);
}
/*}}}*/
 
const int oo = 0x3f3f3f3f;
const int maxn = 2e4 + 5;
const int maxm = 5e4 + 5;
const int maxq = 5e4 + 5;
const int Log = 25;

struct edge {
    int u, v, w, id;

    bool operator < (const edge &x) const {
        return w < x.w;
    }
} ;

struct Query {
    int p, v;
} ;
 
int n;
int m;
int q;

int a[maxm];
int c[maxm];

edge d[maxm];
edge S[maxm];
edge E[Log][maxm];

Query Q[maxq];

int fa[maxn];

namespace UnionSet 
{
    void init(int tot)
    {
        for (int i = 1; i <= tot; ++ i) {
            fa[d[i].u] = d[i].u;
            fa[d[i].v] = d[i].v;
        }
    }

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

    inline void Union(int x, int y)
    {
        fa[x] = y;
    }
}

long long ans[maxq];

void UnionNode(int &tot, long long &Ans, int l, int r)
{
    int top = 0;

    UnionSet::init(tot);

    for (int i = l; i <= r; ++ i)
        d[c[Q[i].p]].w = -oo;

    sort(d + 1, d + tot + 1);

    for (int i = 1; i <= tot; ++ i) {
        if (UnionSet::find(d[i].u) != UnionSet::find(d[i].v)) {
            S[++ top] = d[i];
            UnionSet::Union(fa[d[i].u], fa[d[i].v]);
        }
    }

    for (int i = 1; i <= top; ++ i) {
        fa[S[i].u] = S[i].u;
        fa[S[i].v] = S[i].v;
    }

    for (int i = 1; i <= top; ++ i) {
        if (S[i].w == -oo) continue;
        if (UnionSet::find(S[i].u) != UnionSet::find(S[i].v)) {
            Ans += S[i].w;
            UnionSet::Union(fa[S[i].u], fa[S[i].v]);
        }
    }

    top = 0;
    for (int i = 1; i <= tot; ++ i) {
        if (UnionSet::find(d[i].u) != UnionSet::find(d[i].v)) {
            S[++ top] = d[i];
            c[d[i].id] = top;
            S[top].u = fa[d[i].u];
            S[top].v = fa[d[i].v];
        }
    }

    for (int i = 1; i <= top; ++ i)
        d[i] = S[i];

    tot = top;
}

void DelEdge(int &tot, int l, int r)
{
    int top = 0;

    UnionSet::init(tot);

    for (int i = l; i <= r; ++ i)
        d[c[Q[i].p]].w = oo;

    sort(d + 1, d + tot + 1);
    for (int i = 1; i <= tot; ++ i) {
        if (UnionSet::find(d[i].u) != UnionSet::find(d[i].v)) {
            UnionSet::Union(fa[d[i].u], fa[d[i].v]);
            S[++ top] = d[i];
            c[d[i].id] = top;
        }
        else
        if (d[i].w == oo) {
            S[++ top] = d[i];
            c[d[i].id] = top;
        }
    }

    for (int i = 1; i <= top; ++ i) 
        d[i] = S[i];

    tot = top;
}

int tot_edge;

void solve(int l, int r, int now, long long Ans)
{
    int tot = tot_edge;

    if (l == r) 
        a[Q[l].p] = Q[l].v;

    for (int i = 1; i <= tot; ++ i) {
        E[now][i].w = a[E[now][i].id];
        d[i] = E[now][i];
        c[d[i].id] = i;
    }

    if (l == r) {
        UnionSet::init(tot);

        sort(d + 1, d + tot + 1);
        for (int i = 1; i <= tot; ++ i) {
            if (UnionSet::find(d[i].u) != UnionSet::find(d[i].v)) {
                Ans += d[i].w;
                UnionSet::Union(fa[d[i].u], fa[d[i].v]);
            }
        }

        ans[l] = Ans;
        return;
    }

    UnionNode(tot, Ans, l, r);
    DelEdge(tot, l, r);

    for (int i = 1; i <= tot; ++ i) {
        E[now + 1][i] = d[i];
    }

    int mid = l + r >> 1;

    tot_edge = tot; solve(l, mid, now + 1, Ans);
    tot_edge = tot; solve(mid + 1, r, now + 1, Ans);
}

void exec() 
{
    read(n);
    read(m);
    read(q);
    for (int i = 1; i <= m; ++ i) {
        E[0][i].id = i;
        read(E[0][i].u);
        read(E[0][i].v);
        read(E[0][i].w);
        a[i] = E[0][i].w;
    }
    for (int i = 1; i <= q; ++ i) {
        read(Q[i].p);
        read(Q[i].v);
    }

    tot_edge = m;
    solve(1, q, 0, 0);

    for (int i = 1; i <= q; ++ i)
        write(ans[i]);
}

/*{{{*/
int main() 
{
    //ios::sync_with_stdio(false);

    if (fopen(iput.c_str(), "r")) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }
 
    exec();

#ifdef DEBUG_STATUS
    cerr << "\nRunning Time: " << (double) clock() / CLOCKS_PER_SEC << endl;
#endif

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*}}}*/ 

 

BZOJ1095: [ZJOI2007]Hide 捉迷藏
229 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航