Codeforces Round #212 (Div. 2)(二)
接x块联通块。
很容易想到贪心思路，把所有联通块的和放入优先队列中，然后每次取出最小的两个合并即可。。
// Author : JayYe Created Time: 2013-11-15 10:23:26
#include
#include
#include
#include
using namespace std;
typedef __int64 ll;
const int maxn = 100000 + 5;
const int maxm = 100000 + 5;
struct Edge {
int to, next, w, vis;
}edge[maxn<<1];
int head[maxn], E, done[maxn];
void init() {
memset(head, -1, sizeof(head));
E = 0;
}
void newedge(int u, int to, int w) {
edge[E].to = to;
edge[E].w = w;
edge[E].vis = 0;
edge[E].next = head[u];
head[u] = E++;
}
ll dfs(int u) {
done[u] = 1;
ll ret = 0;
for(int i = head[u];i != -1;i = edge[i].next){
if(edge[i].vis) continue;
edge[i].vis = edge[i^1].vis = 1;
ret += edge[i].w;
if(!done[edge[i].to])
ret += dfs(edge[i].to);
}
return ret;
}
struct PP {
ll val;
int be;
PP(ll val, int be) : val(val), be(be) {}
bool operator < (const PP & a) const {
return val > a.val;
}
};
priority_queue qu;
int main() {
init();
int n, m, p, q;
scanf("%d%d%d%d", &n, &m, &p, &q);
int uu = -1, toto = -1;
for(int i = 0;i < m; i++) {
int u, to, w;
scanf("%d%d%d", &u, &to, &w);
newedge(u, to, w);
newedge(to, u, w);
uu = u; toto = to;
}
int tot = 0;
for(int i = 1;i <= n; i++) if(!done[i]){
ll val = dfs(i);
qu.push(PP(val, i));
tot++;
}
if(p + q < tot || tot < q) return puts("NO"), 0;
if(m == 0) {
if(p > 0 && q == n) return puts("NO"), 0;
}
puts("YES");
tot -= q;
int sum = 0;
while(sum < tot) {
PP c1 = qu.top(); qu.pop();
PP c2 = qu.top(); qu.pop();
printf("%d %d\n", c1.be, c2.be);
uu = c1.be, toto = c2.be;
ll add = min(1000000000LL, c1.val + c2.val + 1);
c1.val += add + c2.val;
qu.push(c1);
sum++;
}
for(int i = 0;i < p - tot; i++) {
printf("%d %d\n", uu, toto);
}
return 0;
}