uVA :: 908 :: Re-connecting Computer Sites

Problem : Please find the problem here.

Explanation :The previously chosen path is already given so the first answer is just the sum of the cost of these paths. For the second cost, combine the original edges with the newly given edges and find the weight of the MST associated to that set of edges.

Code : Used Kruskal's Algorithm to find the MST.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 1e6;
int n, t, m, k;
int parent[mxN], ranks[mxN];

struct Edge{
    int src, dst, cost;
    
    Edge(int _src, int _dst, int _cost){
        src = _src;
        dst = _dst;
        cost = _cost;
    }

    bool operator<(Edge const &other){
        return cost < other.cost;
    }
};

void make_set(int v){
    parent[v] = v;
    ranks[v] = 0;
}

int find_set(int v){
    if(v == parent[v]){
        return v;
    }
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a != b){
        if(ranks[a] < ranks[b]){
            swap(a, b);
        }
        parent[b] = a;
        if(ranks[a] == ranks[b]){
            ranks[a]++;
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    ofstream fout("out");
    bool first = 1;

    while(cin >> n){
        int src, dst, cost;
        vector<Edge> new_edges;
        int ans1 = 0, ans2 = 0;
        for(int i = 0; i < n-1; i++){
            cin >> src >> dst >> cost;
            //chosen_edges.emplace_back(Edge(src, dst, cost));
            ans1 += cost;
        }
        cin >> k;
        for(int i = 0; i < k; i++){
            cin >> src >> dst >> cost;
            new_edges.push_back(Edge(src, dst, cost));
        }
        cin >> m;
        for(int i = 0; i < m; i++){
            cin >> src >> dst >> cost;
            new_edges.emplace_back(Edge(src, dst, cost));
        }

        for(int i = 0; i < (int)new_edges.size(); i++){
            make_set(i);
        }

        sort(new_edges.begin(), new_edges.end());
        for(Edge e : new_edges){
            if(find_set(e.src) != find_set(e.dst)){
                ans2 += e.cost;
                union_sets(e.src, e.dst);
            }
        }
        if(!first){
            cout << '\n';
        }else{
            first = 0;
        }
        cout << ans1 << '\n';
        cout << ans2 << '\n';
    }
    return 0;
}

Uva :: 11631 :: Dark roads

Problem : Please find the problem here.

Explanation : The answer is the total weight of the graph minus the weight of the minimum spanning tree(MST).

Code : Used Kruskal's Algorithm to find the MST.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 2e5;
int n, m;
int parent[mxN], ranks[mxN];

struct Edge{
    int src, dst, weight;
    bool operator<(Edge const& other){
        return weight < other.weight;
    }
    Edge(int _src, int _dst, int _weight){
        src = _src;
        dst = _dst;
        weight = _weight;
    }
};
void make_set(int v){
    parent[v] = v;
    ranks[v] = 0;

}

int find_set(int v){
    if(v == parent[v]){
        return v;
    }
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b){
    a = find_set(a);
    b = find_set(b);
    if(a != b){
        if(ranks[a] < ranks[b]){
            swap(a, b);
        }
        parent[b] = a;
        if(ranks[a] == ranks[b]){
            ranks[a]++;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin >> n >> m && (n || m)){
        
        int src, dst, weight;
        int total_weight = 0;
        vector<Edge> edges, result;
        int cost = 0;
        // make disjoint sets for each of the vertex in the graph;
        for(int i = 0; i < n; i++){
            make_set(i);
        }

        // add edges;
        for(int i = 0; i < m; i++){
            cin >> src >> dst >> weight;
            total_weight += weight;
            //cout << src << ' ' << dst << ' ' << weight << '\n';
            edges.push_back(Edge(src, dst, weight));
        }

        // one can sort this edges or just store the edges in the priority queue with required operator..;
        sort(edges.begin(), edges.end());
        // now the unification process.
        // pick all the edges from first to last and if the ends of current edge belong to different set,
        // these sets are combined  and the edge is added to the result.
        for(Edge e : edges){
            if(find_set(e.src) != find_set(e.dst)){
                cost += e.weight;
                result.push_back(e);
                union_sets(e.src, e.dst);
            }
        }
        // After iterating through all the edges, all the vertices will belong to the same subtree.
        cout << total_weight-cost << '\n';
        // The answer is the total_weight of the graph minus the weight of the MST;
    }
    return 0;
}

UVa :: 10986 :: Sending email

Problem : Please find the problem here.

Explanation : Given an undirected weighted graph, find the minimum distance between two given nodes. The problem is naive and clearly suggested to use the algorithm suited to calculate the SSSP.

Code : Used Dijkstra's Algorithm.

#include <bits/stdc++.h>
using namespace std;

const int mxN = 2e5;
int n, m, s, t, d[mxN];
vector<array<int, 2>> adj[mxN];
bool vis[mxN];


void init(){
    memset(vis, false, sizeof(vis));
    for(int i = 0; i < n; i++){
        adj[i].clear();
        d[i] = INT_MAX;
    }
}

void solve(){
    cin >> n >> m >> s >> t;
    init();
    for(int i = 0, u, v, w; i < m; i++){
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    priority_queue<array<int,2>, vector<array<int, 2>>, greater<array<int, 2>>> pq;
    d[s] = 0;
    pq.push({0, s}); 
    while(pq.size()){
        array<int, 2> uu = pq.top();
        pq.pop();
        int u = uu[1];
        if(vis[u]) continue;
        vis[u] = 1;
        for(array<int, 2> vv : adj[u]){
            int v = vv[0], w = vv[1];
            if(d[v] > d[u]+w){
                d[v] = d[u]+w;
                pq.push({d[v], v});
            }
        }
    }
    if(d[t] == INT_MAX) cout << "unreachable\n";
    else cout << d[t] << '\n';
    
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int test_case;
    cin >> test_case;
    for(int i = 1; i <= test_case; i++){
        cout << "Case #" << i << ": ";
        solve();
    }
    return 0;
}