CCC 2017 S4 Minimum Cost Flow

    1#include <bits/stdc++.h>
    2using namespace std;
    3typedef long long ll;
    4const long long INF = 1e17; //❄️
    5vector<int> parent;
    6struct edge {
    7    int u, v, w, s;
    8    edge(int uu, int vv, int ww, int ss) : u(uu), v(vv), w(ww), s(ss) {}
    9    bool operator<(const edge& o) const {
    10        if (o.w != w) return w < o.w;
    11        return s > o.s;
    12    }
    13};
    14int find(int x) {
    15    return parent[x] == x ? x : parent[x] = find(parent[x]);
    16}
    17void unite(int x, int y) {
    18    x = find(x); y = find(y);
    19    parent[x] = y;
    20}
    21int main() {
    22    ios::sync_with_stdio(0); cin.tie(0); 
    23    int n, m, d; cin >> n >> m >> d;
    24    vector<edge> edges;
    25    parent.resize(n + 1);
    26    for (int i = 1; i <= n; i++) parent[i] = i;
    27    for (int i = 0; i < m; i++) {
    28        int u, v, w; cin >> u >> v >> w;
    29        edges.emplace_back(u, v, w, i < n - 1 ? 1 : 0);
    30    }
    31    sort(edges.begin(), edges.end());
    32    vector<edge> use;
    33    int cnt = 0, ans = 0, last = -1;
    34    for (int i = 0; i < edges.size(); i++) {
    35        if (cnt == n - 1) break;
    36        auto[u, v, w, s] = edges[i];
    37        if (find(u) != find(v)) {
    38            use.emplace_back((edge){u, v, w, s});
    39            unite(u, v);
    40            cnt++;
    41            last = i;
    42            if (!s) {
    43                ans++;
    44            }
    45        }
    46    }
    47    if (edges[last].w <= d && edges[last].s == 0) {
    48        for (int i = 1; i <= n; i++) parent[i] = i;
    49        for (int i = 0; i < last; i++) {
    50            auto[u, v, w, s] = edges[i];
    51            if (w == edges[last].w && s == edges[last].s) continue;
    52            if (find(u) != find(v)) unite(u, v);
    53        }
    54        for (int i = last + 1; i < edges.size(); i++) {
    55            auto[u, v, w, s] = edges[i];
    56            if (w <= d && s && find(u) != find(v)) {
    57                ans--; break;
    58            } 
    59        }
    60    }
    61    cout << ans << '\n';
    62    return 0;
    63}