Chinese

#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <limits>
#include <algorithm>
#include <set>


//#define DEBUG

#ifdef DEBUG
#define OUT_FILE_NAME "stdout"
#else
#define OUT_FILE_NAME "chinese.out"
#endif

#define IN_FILE_NAME "chinese.in"


class Vertex {
private:
    class DistVertex {
    public:
        int weight;
        int v_num;

        DistVertex() : DistVertex(-1, -1) {}

        DistVertex(int _num, int _weight) :
                v_num{ _num },
                weight{ _weight } { }

    };

public:
    typedef std::vector<DistVertex>::iterator ChildIterator;
    typedef enum { white, gray, black } Color;

    Color color = white;
    std::vector<DistVertex> child;

};

typedef std::vector<Vertex> Graph;

void graphColorClear(Graph &graph) {
    for (auto &item : graph) {
        item.color = Vertex::Color::white;
    }
}

bool existWaysToAllVertexesDFS(Graph &graph, int root) {
    std::set<int> visited;
    if (graph[root].color != Vertex::Color::white)
        return true;

    // DFSPair includes vertex number and iterator to the next child of vertex to see
    typedef std::pair<int, Vertex::ChildIterator> DFSPair;
    std::stack<DFSPair> stack;
    graph[root].color = Vertex::Color::gray;
    stack.emplace(root, graph[root].child.begin());

    while (!stack.empty()) {
        DFSPair temp_pair = stack.top();
        stack.pop();

        if (temp_pair.second == graph[temp_pair.first].child.end()) {
            graph[temp_pair.first].color = Vertex::Color::black;
            visited.emplace(temp_pair.first);
        }
        else {
            stack.emplace(temp_pair.first, next(temp_pair.second));

            if (graph[temp_pair.second.operator*().v_num].color == Vertex::Color::white) {
                graph[temp_pair.second.operator*().v_num].color = Vertex::Color::gray;
                stack.emplace(temp_pair.second.operator*().v_num, graph[temp_pair.second.operator*().v_num].child.begin());
            }
        }
    }

    graphColorClear(graph);

    return graph.size() == visited.size();
}

void DFSTopSort(Graph &graph, int root, std::vector<int> &visit_order) {
    if (graph[root].color != Vertex::Color::white) {
        return;
    }
    graph[root].color = Vertex::Color::black;

    for (auto v_to : graph[root].child) {
        if (graph[v_to.v_num].color == Vertex::Color::white) {
            DFSTopSort(graph, v_to.v_num, visit_order);
        }
    }
    visit_order.push_back(root);
}

bool DFSComponentSearch(Graph &transposed_graph, int root, std::vector<int> &components, int component_num) {
    if (transposed_graph[root].color != Vertex::Color::white) {
        return false;
    }

    transposed_graph[root].color = Vertex::Color::black;
    components[root] = component_num;

    for (auto v_to : transposed_graph[root].child) {
        if (transposed_graph[v_to.v_num].color == Vertex::Color::white) {
            DFSComponentSearch(transposed_graph, v_to.v_num, components, component_num);
        }
    }
    return true;
}

int condensateByComponents(Graph &graph, std::vector<int> &components) {
    Graph transposed_graph(graph.size());

    for (int i = 0; i < graph.size(); ++i) {
        for (auto &item : graph[i].child) {
            transposed_graph[item.v_num].child.emplace_back(i, item.weight);
        }
    }

    std::vector<int> visit_order;
    for (int v_start = 0; v_start < graph.size(); ++v_start) {
        DFSTopSort(graph, v_start, visit_order);
    }
    graphColorClear(graph);

    std::reverse(visit_order.begin(), visit_order.end());

    int component_num = 0;
    for (int v : visit_order) {
        if (DFSComponentSearch(transposed_graph, v, components, component_num)) {
            component_num++;
        }

    }
    graphColorClear(transposed_graph);

    return component_num;
}

long long calcMSTWeight(Graph &graph, int root) {
    std::vector<int> edge_min_weight(graph.size(), std::numeric_limits<int>::max());
    for (auto &v_start : graph) {
        for (auto const &v_finish : v_start.child) {

            int v_weight = v_finish.weight;
            int v_to = v_finish.v_num;
            edge_min_weight[v_to] = (v_weight < edge_min_weight[v_to]) ? v_weight : edge_min_weight[v_to];
        }
    }

    long long mst_weight = 0;
    for (int i = 0; i < graph.size(); ++i) {
        mst_weight += (i != root) ? edge_min_weight[i] : 0;
    }

    Graph zero_graph(graph.size());
    for (int v_start = 0; v_start < graph.size(); ++v_start) {
        for (int v_finish = 0; v_finish < graph[v_start].child.size(); ++v_finish) {

            int v_to = graph[v_start].child[v_finish].v_num;
            int weight = graph[v_start].child[v_finish].weight;

            if (weight == edge_min_weight[v_to]) {
                zero_graph[v_start].child.emplace_back(v_to, 0);
            }
        }
    }

    if (existWaysToAllVertexesDFS(zero_graph, root)) {
        return mst_weight;
    }

    std::vector<int> components(graph.size());
    int components_count = condensateByComponents(zero_graph, components);

    Graph cond_graph(static_cast<unsigned long>(components_count));
    for (int v_start = 0; v_start < graph.size(); ++v_start) {
        for (auto const &v_finish : graph[v_start].child) {
            int v_to = v_finish.v_num;
            int weight = v_finish.weight;

            if (components[v_start] != components[v_to]) {
                cond_graph[components[v_start]].child.emplace_back(components[v_to], weight - edge_min_weight[v_to]);
            }
        }
    }
    return mst_weight + calcMSTWeight(cond_graph, components[root]);
}

int main() {
    std::ifstream fin(IN_FILE_NAME);

    uint32_t v_count, e_count;
    fin >> v_count >> e_count;

    Graph graph(v_count);

    for (int i = 0; i < e_count; ++i) {
        int v, w;
        int weight;
        fin >> v >> w >> weight;

        graph[v - 1].child.emplace_back(w - 1, weight);
    }
    fin.close();

    std::ofstream fout(OUT_FILE_NAME);

    if (existWaysToAllVertexesDFS(graph, 0)) {
        fout << "YES\n" << calcMSTWeight(graph, 0) << '\n';
    }
    else {
        fout << "NO\n";
    }
    fout.close();
    return 0;
}