Editorial for CCC '17 S4 - Minimum Cost Flow


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: kobortor, Kirito

For up to 11 of the 15 available marks, we note that D = 0. We can first sort all edges by weight, breaking ties by taking the edge which appeared earlier in the input. We then run a standard MST algorithm, keeping track of the number of new edges in the MST.

Time Complexity: \mathcal O(M \log M)

Full solution

For the full solution, we have to account for when D \neq 0.

There are two solutions to do this

Solution 1:

To find the best value, we take the total of the MST from before and subtract at most D from the largest edge. Store this value in some variable for now.

Next, we try to see if we can reduce the number of days required by 1. To do this, we take each unused original edge and try to use it to replace a new edge in the MST. To find the largest value to remove, we use a sparse tree to find the largest value in \mathcal O (\log N) time. The new cost will be old MST cost + new edge - removed edge - min*(D, largest remaining edge). If this equals the best value we can get in the old edge, we reduce the days required by 1 and stop trying.

Solution 2:

First, we generate an MST similarly to what we did for the first 11 points. However, we notice that only edges with weight equal to that of the heaviest edge will be replaced. Let us can this weight w_l.

Then, we run Kruskal's algorithm, with a slight modification: if the edge's weight is less than w_l or was in the original MST and has a weight equal to w_l, then we add it into the MST like in the standard algorithm. However, if the weight of the edge is \le D and is also an old edge, then it can replace one of the edges we used, thus decreasing the number of days required by 1.

Time Complexity: \mathcal O (M \log M)

Sample Solution — D

import std.stdio;
import std.algorithm;

struct edge {
    int src, des, w, o;

    int opCmp (ref const edge e) const {
        if(w != e.w) return w - e.w;
        else return o - e.o;
    }
};

const int MAXN = 100004, MAXM = 200004;
int N, M, D, ee, weight, days;
int[MAXN] ds;
edge[] edges;

void init() {
    for(int i=1;i<=N;i++) ds[i] = i;
}

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

bool connected(int x, int y) {
    return find(x) == find(y);
}

bool merge(int x, int y) {
    int xr = find(x), yr = find(y);
    if(xr ^ yr) {
        ds[xr] = yr;
        return 1;
    }
    return 0;
}

void main() {
    scanf("%d%d%d", &N, &M, &D);
    for(int i=1, a, b, c;i<=M;i++) {
        scanf("%d%d%d", &a, &b, &c);
        if(i < N)
            edges ~= edge(a, b, c, 0);
        else
            edges ~= edge(a, b, c, 1);
    }
    edges.sort();
    init();
    int i, maxe=0;
    for(i=0;i<edges.length;i++) {
        if(ee == N - 1) break;
        auto e = edges[i];
        if(merge(e.src, e.des)) {
            ee++;
            maxe = e.w;
            if(e.o)
                days ++;
        }
    }
    //Either days, or days - 1 is the answer
    //Want to replace a new edge with an old edge with same or lesser cost
    if(edges[i-1].o) {
        init();
        foreach(e;edges) {
            if(!connected(e.src, e.des)) {
                if(e.w < maxe || (e.w == maxe && !e.o))
                    merge(e.src, e.des);
                else if(!e.o && e.w <= D) {
                    printf("%d", days - 1);
                    return;
                }
            }
        }
    }
    printf("%d", days);
}

Comments


  • 2
    RyanLi  commented on Feb. 2, 2020, 12:06 p.m.

    Let us can this weight wl

    Typo on call