并查集瞎搞搞就行, 有点小坑点。
#include<bits/stdc++.h> #define LL long long #define fi first #define se second #define mk make_pair #define PLL pair<LL, LL> #define PLI pair<LL, int> #define PII pair<int, int> #define SZ(x) ((int)x.size()) #define ull unsigned long long using namespace std; const int N = 2e5 + 7; const int inf = 0x3f3f3f3f; const LL INF = 0x3f3f3f3f3f3f3f3f; const int mod = 1e9 + 7; const double eps = 1e-8; const double PI = acos(-1); int n, m, p, q, num, fa[N], U = -1, V = -1; LL cost[N]; vector<PII> vc; int getRoot(int x) { return fa[x] == x ? x : fa[x] = getRoot(fa[x]); } int main() { scanf("%d%d%d%d", &n, &m, &p, &q); for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= m; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); U = u; V = v; int x = getRoot(u); int y = getRoot(v); if(x == y) { cost[x] += w; } else { fa[x] = y; cost[y] += cost[x] + w; } } priority_queue<PLI, vector<PLI>, greater<PLI> > que; for(int i = 1; i <= n; i++) if(getRoot(i) == i) que.push(mk(cost[i], i)), num++; int need = num - q; if(need < 0 || need > p) { puts("NO"); return 0; } while(need--) { p--; int u = que.top().se; que.pop(); int v = que.top().se; que.pop(); int x = getRoot(u), y = getRoot(v); vc.push_back(mk(u, v)); U = u, V = v; LL ret = min(1000000000ll, cost[x] + cost[y] + 1); cost[y] += cost[x] + ret; que.push(mk(cost[y], y)); } if(p && U == -1) { puts("NO"); return 0; } while(p--) { vc.push_back(mk(U, V)); } puts("YES"); for(auto& t : vc) printf("%d %d\n", t.fi, t.se); return 0; } /* */