ferinの競プロ帳

競プロについてのメモ

codeforces #212 div2 D. Fools and Foolproof Roads

問題ページ Problem - D - Codeforces

概要

n頂点m辺の重み付き無向グラフが与えられる。このグラフに辺を張る操作をp回行うことで連結成分数がq個になるようにしたい。
辺を張るときは

  • 同じ連結成分内の頂点なら1000
  • 違う連結成分の頂点ならばmin(10^9, 連結成分の辺の重みの和)

のコストがかかる。
条件を満たす操作があるのか、そのうちかかるコストが最小となるような操作はどのようなものかを答えろ

考えたこと

  • 連結成分について扱うしunionfind?
  • unionfindで各連結成分について辺の重みの和をもっておくとよさそう
  • 最初の時点で連結成分数がqより少なければ不可能
  • 同じ連結成分内の頂点をつなぐ操作を違う連結成分の頂点をつなぐより優先すべきか考えると多分そんな状況はない
  • 違う連結成分の頂点をつなぐコストが増えるし連結成分数を減らすことはできないため
  • したがって連結成分数をq個にしたあとさらに操作をしないといけないときのみ同じ連結成分の頂点をつなげばよい
  • 逆に連結成分数がすでにq個で操作しないといけないのに2頂点以上の連結成分がなければ不可能
  • つなぐ連結成分はどうするべきか
  • 辺の重みの和が小さい連結成分から貪欲につなげばいい気持ちになったので貪欲を書くと通った

unionfindで連結成分、priority_queueで(辺の重みの和、どの連結成分か)について管理しながら貪欲
バグとコーナーに気をつけつつ実装する

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

class UnionFind {
public:
  const static int MAX_N = 100010;
  int par[MAX_N];
  int s[MAX_N];
  int w[MAX_N];
  UnionFind() { init(); }
  UnionFind(int n) { init(n); }
  void init() { for(int i=0; i<MAX_N; ++i) par[i] = i, s[i] = 1, w[i] = 0; }
  void init(int n) { for(int i=0; i<n; ++i) par[i] = i, s[i] = 1, w[i] = 0; }
  int find(int x) {
    if(par[x] == x) return x;
    return par[x] = find(par[x]);
  }
  void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if(x == y) return;
    if(s[x] < s[y]) par[x] = y, s[y] += s[x], w[y] += w[x];
    else par[y] = x, s[x] += s[y], w[x] += w[y];
  }
  bool same(int x, int y) { return find(x) == find(y);}
};
UnionFind uf;

VI v[100010];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  int n, m, p, q;
  cin >> n >> m >> p >> q;
  REP(i, m) {
    int x, y, l;
    cin >> x >> y >> l;
    x--, y--;
    uf.unite(x, y);
    uf.w[uf.find(x)] += l;
  }

  priority_queue<PII, vector<PII>, greater<PII>> que;
  vector<bool> used(n, false);
  int cnt = 0;
  REP(i, n) {
    if(used[uf.find(i)]) continue;
    used[uf.find(i)] = true;
    que.push({uf.w[uf.find(i)], uf.find(i)});
    cnt++;
  }

  if(cnt < q) {
    cout << "NO" << endl;
    return 0;
  }

  vector<PII> ans;
  int num = 0;
  while(num < p && cnt > q) {
    PII p1 = que.top(); que.pop();
    PII p2 = que.top(); que.pop();
    uf.unite(p1.second, p2.second);
    if(uf.w[uf.find(p1.second)] >= 1e9) {
      uf.w[uf.find(p1.second)] += 1e9;
    } else {
      uf.w[uf.find(p1.second)]*=2;
      uf.w[uf.find(p1.second)]++;
    }
    cnt--; num++;
    ans.PB({p1.second, p2.second});
    que.push({uf.w[uf.find(p1.second)], uf.find(p1.second)});
  }

  if(num == p) {
    if(cnt > q) {
      cout << "NO" << endl;
    } else if(cnt == q) {
      cout << "YES" << endl;
      for(auto i: ans) {
        cout << i.first+1 << " " << i.second+1 << endl;
      }
    }
    return 0;
  }

  REP(i, n) v[uf.find(i)].PB(i);
  int idx = -1;
  REP(i, n) if(v[i].size() >= 2) idx = i;
  if(idx == -1) {
    cout << "NO" << endl;
    return 0;
  }

  while(num < p) {
    ans.PB({v[idx][0], v[idx][1]});
    num++;
  }

  cout << "YES" << endl;
  for(auto i: ans) {
    cout << i.first+1 << " " << i.second+1 << endl;
  }

  return 0;
}