2017 S4.cpp

/*

2017 S4 - Minimum Cost Flow

Difficulty: Hard

Topics: Minimum Spanning Tree

General idea, we will use Kruskal's MST algorithm to determine the most optimized arrangement of pipes.
When sorting edges for Kruskals, we will sort by cost, then by whether the pipe was original or not for equal cost pipes.

For the first 11 marks, it suffices to just output the number of unoriginal pipes in the optimized plan, since you can only replace one pipe per day.
For the remaining marks, we will have to deal with the enhancer.

The idea is that using the optimized plan generated by Kruskals earlier, we want to keep track of the most expensive pipe.
The reason for this is that by logic we would want to use the enhancer on the most expensive pipe to maximise its value.
If the most expensive pipe is not original and can be zeroed using the enhancer, we want to check for other unused pipes that connect the same buildings and that cost more, but can also be zeroed by the enhancer, indicating we can save a day.
We will then run Kruskals algorithm again, this time however, not adding unoriginal pipes that have a cost equal to that of the most expensive.
Now we search through the slightly more expensive pipes that we normally wouldn't use.

If the pipe is original, does not create a cycle when added, and can have its cost zeroed by the enhancer, then this means we can replace an unoriginal pipe back with an original one

*/

#include <iostream>
#include <vector>
#include <set>
#include <tuple>
#include <utility>

std::vector<int> parent; //Parent vector for Union Find algorithm
std::vector<int> size; //Also for union find

//Determine root of set
int root(int building){
    
    if (parent[building] != building){
        return root(parent[building]);
    }
    
    else{
        return building;
    }
    
}

//Determine if 2 buildings are connected (aka they share the same roots)
bool find(int building1, int building2){
    
    if (root(building1) != root(building2)){
        return false;
    }
    
    else{
        return true;
    }
    
}

//Perform union
void Union(int building1, int building2){
    
    int rootBuilding1 = root(building1);
    int rootBuilding2 = root(building2);
    
    if (size[rootBuilding1] < size[rootBuilding2]){
        parent[rootBuilding1] = rootBuilding2;
        size[rootBuilding2] += size[rootBuilding1];
    }
    
    else{
        parent[rootBuilding2] = rootBuilding1;
        size[rootBuilding1] += size[rootBuilding2];
    }
    
}

int main(){
    
    long long N, M, D;
    std::cin >> N >> M >> D;
    
    //Store pipes in a set so that they're already ordered
    std::set<std::tuple<long long, int, int, int>> pipes; //I will be storing pipes in a tuple, elements are (weight, order in input, source, destination)
    
    //Take in pipes
    for (int i = 0; i < M; i++){
        
        long long weight;
        int source, dest;
        std::cin >> source >> dest >> weight;
        
        pipes.insert(std::make_tuple(weight, i, source, dest));
        
    }
    
    //Set up for union find
    parent.resize(N + 1);
    size.resize(N + 1, 1);
    for (int i = 1; i <= N; i++){
        parent[i] = i;
    }
    
    int pipesUsed = 0; //Minimum spanning tree should have N - 1 pipes
    int newPipes = 0; //Unoriginal pipes
    std::tuple<long long, int, int, int> maxPipe {-999999, -999999, -999999, -999999}; //Most expensive pipe,
    
    //For each pipe
    for (auto pipe: pipes){
        
        if (pipesUsed == N - 1){
            break;
        }
        
        //If a cycle is not created
        if (!find(std::get<2>(pipe), std::get<3>(pipe))){
            
            pipesUsed++;
            Union(std::get<2>(pipe), std::get<3>(pipe));
            
            //If the pipe is unoriginal
            if (std::get<1>(pipe) >= N - 1){
                newPipes++;
            }
            
            maxPipe = pipe; //Update max pipe, pipes are already sorted so the current pipe would be the most expensive
            
        }
        
    }
    
    //Set up for another Kruskals
    parent.clear();
    size.clear();
    parent.resize(N + 1);
    size.resize(N + 1, 1);
    for (int i = 1; i <= N; i++){
        parent[i] = i;
    }
    
    //Kruskals a second time, this time we don't add pipes that are as expensive as the maxPipe and arent original
    for (auto pipe: pipes){
        
        if (!find(std::get<2>(pipe), std::get<3>(pipe))){
            
            //Add pipes that are less than maxPipe since they would always be in the MST, we also want to take pipes that are equal to MST only if they're original since they would be there anyway
            //We don't want unoriginal pipes that are as expensive as the maxPipe, since these are the pipes we're trying to see if we can replace
            if (std::get<0>(pipe) < std::get<0>(maxPipe) || (std::get<0>(pipe) == std::get<0>(maxPipe) && std::get<1>(pipe) < N - 1)){
                Union(std::get<2>(pipe), std::get<3>(pipe));
            }
            
            //If we find a pipe that connects unconnected buildings, is original and has a cost that can be zeroed by the enhancer, then we can decrease the days by 1 since for the remaining pipes, we can just fill in the same as before
            else if (std::get<0>(pipe) <= D && std::get<1>(pipe) < N - 1){
                newPipes--;
                break;
            }
            
        }
        
    }
    
    std::cout << newPipes;

    return 0;
    
}