問題

E – MST + 1

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2021/1/15 リアルタイム参加。解法わからず。

解法

• グラフとクエリの情報をあらかじめ取得しておき、重みで昇順に並べ替えておく。
• グラフ \(G\) の辺でつなぐ前にクエリの辺がつなぐことができる場合は、そのクエリは Yes になる。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 62;
// const int INF = 1001001001;

/**
 * q:
 *  -1 = グラフG に含まれている
 *  それ以外 = クエリ(Q)の番号
 */
struct Edge {
  ll w;
  int u, v;
  int q;
};

// 比較関数
bool cmp(const Edge& a, const Edge& b) {
  if(a.w < b.w) {
    return true;
  }
  return false;
}

int main() {
  int N, M, Q;
  cin >> N >> M >> Q;

  vector<Edge> edges;

  rep(i, M) {
    int a, b;
    ll c;
    cin >> a >> b >> c;
    a--;
    b--;
    Edge e;
    e.u = a;
    e.v = b;
    e.w = c;
    e.q = -1;
    edges.emplace_back(e);
  }

  rep(i, Q) {
    int u, v;
    ll w;
    cin >> u >> v >> w;
    u--;
    v--;
    Edge e;
    e.u = u;
    e.v = v;
    e.w = w;
    e.q = i;
    edges.emplace_back(e);
  }

  sort(edges.begin(), edges.end(), cmp);

  dsu uf(N);

  vector<string> ans(Q, "No");

  int n = edges.size();
  rep(i, n) {
    Edge e = edges[i];
    if(uf.same(e.u, e.v)) {
      continue;
    }
    if(e.q != -1) {
      ans[e.q] = "Yes";
    } else {
      uf.merge(e.u, e.v);
    }
  }

  rep(i, Q) { cout << ans[i] << endl; }
  return 0;
}