Bob's Problem - trees, greedy

Bob was in trouble.He rubbed the magic ring on his finger, and you came out of the ground.

You are given an undirected graph GG which contains nn vertices labelled from 11 to nn, with mm weighted edges between them coloured in black or white.You have to choose some edges in GG such that there is at least one path between any two vertices only passing by selected edges, and you can select no more than kk white edges.There may be multiple available strategies to determine these edges, and you are asked to find out the way with a maximum total weight of edges.

Input

The first line contains an integer TT (1\leq T\leq 5)1≤T≤5) indicating the number of test cases.

For each test case, the first line contains three integers n~(1 \le n \le 50000), mn (1≤n≤50000),m and k~(1\le k\le m \le 500000)k (1≤k≤m≤500000).

Each of the following mm lines contains four integers u, v~(1\le u,v\le n), w~(0\le w\le 100000)u,v (1≤u,v≤n),w (0≤w≤100000) and c~(0\le c\le 1)c (0≤c≤1) describing an edge of weight ww and colour cc between the uu-th vertex and the vv-th vertex. Here an edge is white if c = 1c=1, or black if c = 0c=0.

Note that there may be multiple edges between some vertices, and self-loops are also allowed.

Output

For each test case, output a single line with an integer indicating the maximum total weight of selected edges, or output -1 if there is no solution for the given graph.

样例输入复制

1
5 6 2
1 2 0 0
1 3 5 1
1 5 1 0
2 3 6 1
2 4 2 0
3 4 7 1

样例输出复制

16
先扫一遍，把所有黑色边连上，然后在扫一遍白色边，用从大到小权值的白边使得整个图连通，如果用了k条都做不到输出-1，否则如果k条以内做到了，就用满k条白边
代码如下

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(0), cin.tie(0)
template<typename T> void debug(T x) { cerr << x << " \n";}

template<typename T, typename... Args> void debug(T x, Args... args) {
    cerr << x << " | ";
    debug<T>(args...);
}

const int N = 100005;
struct E {
    int u, v, w;
    E (int u = 0, int v = 0, int w = 0) : u(u), v(v), w(w){}
}e[N]; 
int fa[N];

int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int u, int v) {
    u = find(u);
    v = find(v);
    fa[u] = v;
}

bool same(int u, int v) {
    return find(u) == find(v);
}

#define all(x) (x).begin(), (x).end()
void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    iota(fa, fa + n + 1, 0);
    int ans = 0;
    vector<E> white;
    for (int i = 0; i < m; i++) {
        int u, v, w, c;
        cin >> u >> v >> w >> c;
        if (c == 0) {
            //debug("u, v:");
            //debug(u, v);
            merge(u, v);
            ans += w;
        } else {
            white.emplace_back(u, v, w);
        }
    }
    sort(all(white), [&](E a, E b) {
        return a.w > b.w;
    });
    vector<int> vis(m + 1, 0);
    int cnt = 0;
    for (int i = 0; i < white.size(); i++) {
        auto [u, v, w] = white[i];
        if (!same(u, v) && cnt < k) {
            //debug("u, v:");
            //debug(u, v);
            merge(u, v);
            vis[i] = 1;
            ans += w;
            cnt += 1;
        }
    }
    set<int> now_fa;
    for (int i = 1; i <= n; i++) {
        now_fa.insert(find(i));
    }
    if (now_fa.size() == 1) {
        for (int i = 0; i < white.size(); i++) {
            if (vis[i]) continue;
            auto [u, v, w] = white[i];
            if (cnt < k) {
                //debug("u, v:");
                //debug(u, v);
                merge(u, v);
                vis[i] = 1;
                ans += w;
                cnt += 1;
            }
        }
        cout << ans << "\n";
    } else {
        cout << -1 << "\n";
    }
}
signed main() {
    IOS;
    int T;
    cin >> T;
    while (T--) {
        solve();
    }


    return 0;
}