TakahiroNakamori

TakahiroNakamori

ナカモリタカヒロ

 
 

MST + 1

問題

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

記録

解法

コード例

#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;
}