In my previous article, I haven’t written anything about problem E except the statement that I had not read the problem yet.

Ok, here it is.

Problem E

This problem is the mathematical one. To solve this problem, you need to know some elementary Graph Theory theorem such as: The theorem proposed by Euler about Euler Circuit and Euler Path, Kruskal’s Theorem in Minimum Spanning Tree, etc.

Let G = (V, E) be the graph given in the input (the one which edges are the possible worm-holes in the graph).

Case 1: If G contains at least three components, the output should always be -1. Why? Let’s think a bit. Suppose you’re given a query a and b, if G contains three components or more, there should be a component C such that C doesn’t contain both a and b. We can construct a graph G’ = (V’, E’) in such a way that G’ is constructed by adding some additional edges to G to link all components in G (so G’ is connected), and all those additional edges are bridge. It is clear that whenever the supervisor go from a to somewhere inside C, he was trapped there because he cannot cross the bridge twice and there is no wormholes connecting C to any components contain either a or b. ■

Case 2: If G contains two components, there are two cases: If a and b is in the same component, the output should be -1 with the same reasoning as the one presented above. Otherwise, the answer is the sum of total weight of spanning trees in each component. So, solving the optimization problem is easy. Why? It is an MST problem. The reason why we should compute the spanning forest is Baldman should select some edges in each component such that the graph formed by those edges (in one component) is connected. Otherwise, the graph formed will contain more than two components and hence it’s not the solution (see Case 1). And then, try to convince yourself that the connected graph with smallest total edge’s weight possible is MST. So, case 2 is clear. ■

Case 3: This is the most difficult case, I think. For each query a and b, Baldman may not select some edges such that the resulting graph contains more than two components (see case 1). So, he can select those edges, such that it contains either one or two components. Which one is more optimal? Of course two component graph will have smaller total edge’s weight than one component graph. Because we can remove an edge from one component graph to construct a two component graph with smaller total edge’s weight. The rest is a bit complex. We want to form two disjoint MST-s from a given connected graph such that the total weight of both MST is as small as possible. It can be shown that those optimal two disjoint MST-s can be formed by removing an edge from the MST of the graph. Since a and b should be in different components, the edge that we should remove is the one in the path from a to b in the MST. And of course, it should be the one with largest weight. To do this, precompute the MST, get a data structure that can query the maximum weight edge from a to b in the MST. The data structure is quite tricky. Since we know that the path from a to be should pass through the LCA of a and b, and LCA can be preprocessed in O(n lg n) time, we can modify LCA algorithm for this. If you don’t know LCA (Lowest Common Ancestor) before, please read some other tutorial first. Otherwise, you will getting lost in reading the rest of this explanation.

Let LCA[lg][v] is the ancestor of v which distance from v is 2^lg. Let RMAX[lg][v] is the maximum edge in the path from v to LCA[lg][v]. It’s easy to see that:

RMAX[lg][v] = max (RMAX[lg – 1][LCA[lg – 1][v]], RMAX[lg – 1][v])

Precompute RMAX while doing the LCA precomputation will be easy. Then, how to do the query part? Easy. When you do query in LCA, the LCA[lg][v] table above was needed to jump from a vertex to it’s ancestor. Everytime you do a jump with the help of LCA[lg][v], take RMAX[lg][v] as the candidate solution. In other words, the largest RMAX[lg][v] seen when doing those jumps in the LCA should be the solution. Then, answer should be: total_weight_of_MST – query (a, b). ■

Source code:

#define MAXV 100000

LL V, E;
LL total;
vector <PII> G[MAXV + 2];
vector <PII> forest[MAXV + 2];
vector <pair <LL, PII> > Edges;

LL rank[MAXV + 2], parent[MAXV + 2];
LL LCA[20][MAXV + 2];
LL RMAX[20][MAXV + 2];

inline void initDJ () {
    REP (i, V) {
        rank[i] = 0;
        parent[i] = i;
    }
}

inline LL find (LL x) {
    if (parent[x] == x) return x;
    return parent[x] = find (parent[x]);
}

inline void merge (LL x, LL y) {
    LL rootX = find (x), rootY = find (y);
    if (rank[rootX] == rank[rootY]) rank[rootX]++;
    if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
    else parent[rootX] = rootY;
}

LL color[MAXV + 2];
LL ncol;
LL L[MAXV + 2];

inline void dfs (LL v, LL p, LL col, LL lvl) {
    L[v] = lvl;
    color[v] = col;
    REP (i, SIZE (forest[v])) {
        LL w = forest[v][i].F;
        LL weight = forest[v][i].S;
        if (color[w] == -1) {
            LCA[0][w] = v;
            RMAX[0][w] = weight;
            dfs (w, v, col, lvl + 1);
        }
    }
}

inline void initLCA () {
    FOR (lg, 1, 19) {
        REP (i, V) {
            if (LCA[lg - 1][i] == -1) continue;
            LCA[lg][i] = LCA[lg - 1][LCA[lg - 1][i]];
            RMAX[lg][i] = MAX (RMAX[lg - 1][LCA[lg - 1][i]], RMAX[lg - 1][i]);
        }
    }
}

inline LL query (LL a, LL b) {
    LL ret = 0;

    if (L[a] < L[b]) swap (a, b);

    REPD (lg, 20) {
        if (LCA[lg][a] != -1 && L[LCA[lg][a]] >= L[b]) {
            ret = MAX (ret, RMAX[lg][a]);
            a = LCA[lg][a];
        }
    }

    if (a == b) return ret;

    REPD (lg, 20) {
        if (LCA[lg][a] != LCA[lg][b]) {
            ret = MAX (ret, RMAX[lg][a]);
            ret = MAX (ret, RMAX[lg][b]);
            a = LCA[lg][a];
            b = LCA[lg][b];
        }
    }

    ret = MAX (ret, RMAX[0][a]);
    ret = MAX (ret, RMAX[0][b]);

    return ret;
}

inline void doKruskal () {
    initDJ ();

    total = 0;

    sort (ALL (Edges));

    REP (i, SIZE (Edges)) {
        LL a, b, c;
        a = Edges[i].S.F;
        b = Edges[i].S.S;
        c = Edges[i].F;

        if (find (a) != find (b)) {
            merge (a, b);
            forest[a].PB (MP (b, c));
            forest[b].PB (MP (a, c));
            total += c;
        }
    }
}

inline void readInput () {
    scanf ("%lld%lld", &V, &E);

    REP (i, E) {
        LL a, b, c;
        scanf ("%lld%lld%lld", &a, &b, &c);
        a--; b--;
        G[a].PB (MP (b, c));
        G[b].PB (MP (a, c));
        Edges.PB (MP (c, MP (a, b)));
    }
}

inline void colorComps () {
    RESET (LCA, -1);
    RESET (RMAX, -1);
    RESET (color, -1);

    ncol = 0;

    REP (i, V) {
        if (color[i] == -1)
            dfs (i, -1, ncol++, 0);
    }
}

int main () {
    readInput ();
    doKruskal ();
    colorComps ();
    initLCA ();

    LL Q;
    scanf ("%lld", &Q);

    while (Q--) {
        LL a, b;
        scanf ("%lld%lld", &a, &b);
        a--; b--;
        if (ncol == 1)
            printf ("%lld\n", total - query (a, b));
        else if (ncol == 2 && find (a) != find (b))
            printf ("%lld\n", total);
        else
            puts ("-1");
    }

    return 0;
}

It’s a nice problem. Actually, it’s not hard to figure out the solution. The hardest part in this problem is to divide all cases carefully and code that long code without any mistakes.

Advertisements