ARC095 C - Many Medians
問題ページ
C - Many Medians
考えたこと
- 中央値を取りうるのはa[n/2-1]かa[n/2]の二択
- n/2番目以降ならa[n/2-1]、それ以外ならa[n/2]
- ソートすればいいのになぜか座圧を書く
- 座圧を書いたあとsampleを見て気づいてソートに書き直す
- 出すと通る
無駄に時間かけすぎ
ソースコード
#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; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; VI a(n); vector<PII> v(n); REP(i, n) cin >> a[i], v[i] = {a[i], i}; sort(ALL(v)); int x = v[n/2-1].first, y = v[n/2].first; VI ans(n); REP(i, n) { if(i < n/2) { ans[v[i].second] = y; } else { ans[v[i].second] = x; } } REP(i, n) cout << ans[i] << endl; return 0; }
AOJ2304 Reverse Roads
問題ページ
Reverse Roads | Aizu Online Judge
考えたこと
- 有向グラフの辺を反転することでs-tフローを最大化する
- 与えられた辺を無向辺のように扱って両方の向きに辺を張ってフローを流す
- 最大フローの値はこれで求まる
- 反転すべき辺を求めるのには残余グラフを使うとよさそう
- 辺の容量が0で逆辺が1の辺があればその向きにその辺を使っている
- 使ってる方向が本来与えられた向きと逆であればその辺を反転したとして出力
残余グラフはじめて使った
ソースコード
#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; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; const int MAX_N = 300; struct edge {int to, cap, rev;}; vector<edge> G[MAX_N+1]; bool used[MAX_N+1]; void add_edge(int from, int to, int cap) { G[from].push_back((edge){to, cap, (int)G[to].size()}); G[to].push_back((edge){from, 0, (int)G[from].size()-1}); } int dfs(int v, int t, int f) { if(v == t) return f; used[v] = true; REP(i, G[v].size()) { edge &e = G[v][i]; if(!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if(d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t) { int flow = 0; while(true) { memset(used, 0, sizeof(used)); int f = dfs(s, t, INF); if(f == 0) return flow; flow += f; } } int g[305][305]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n, m, s, t; cin >> n >> m; REP(i, m) { int x, y; cin >> x >> y; x--, y--; g[y][x] = i+1; add_edge(x, y, 1); add_edge(y, x, 1); } cin >> s >> t; s--, t--; cout << max_flow(s, t) << endl; VI ans; REP(i, n) { for(edge e: G[i]) { // i->e.toの辺について if(e.cap == 0 && G[e.to][e.rev].cap == 1) { if(g[i][e.to]) { ans.PB(g[i][e.to]); } } } } sort(ALL(ans)); ans.erase(unique(ALL(ans)), ans.end()); cout << ans.size() << endl; for(int i: ans) cout << i << endl; return 0; }
AOJ2382 KingSlime
問題ページ
King Slime | Aizu Online Judge
考えたこと
- 縦横で同じ軸にいるスライムは移動1回でくっつけられそう
- sample1を見ると縦横で同じ軸にいるスライムをつないでいってその連結成分にいるスライムは移動1回でまとめられそう
- つまり(連結成分の大きさ-1)回移動することになりそう
- 異なる連結成分に属するスライム同士をくっつけるには全て端に寄せてつなげていくことになりそう
- 端に寄せるのに(連結成分数)回、寄せたあとくっつけるのに(連結成分数-1)回かかる
- ここで端に寄せるときにそもそも端にいるスライムの分は移動させなくて良い
- 同じ辺に複数スライムがいる場合でもそのスライムは同じ連結成分としてまとまるので引くのは1匹分でよい
- 連結成分をまとめるところでO(n^2)でちょっと怖いが8secで定数倍軽いしAOJを信じる
- 連結成分の管理をunionfindでやることにして実装すると通った
ソースコード
#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; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; class UnionFind { public: VI par, s; UnionFind(int n=1e5) { init(n); } void init(int n=1e5) { par.resize(n); s.assign(n, 1); REP(i, n) par[i] = i; } 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] + s[y]; else par[y] = x, s[x] = s[x] + s[y]; } bool same(int x, int y) { return find(x) == find(y);} }; int x[40010], y[40010]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n, h, w; cin >> n >> w >> h; bool flag=false; REP(i, n) { cin >> x[i] >> y[i]; x[i]--, y[i]--; if(x[i]==0 || x[i]==w-1 || y[i]==0 || y[i]==h-1) flag = true; } UnionFind uf(n); REP(i, n) FOR(j, i+1, n) { if(x[i] == x[j] || y[i] == y[j]) { uf.unite(i, j); } } int ret = 0, cnt = 0; REP(i, n) { if(i == uf.find(i)) { ret += uf.s[uf.find(i)] - 1; cnt++; } } if(cnt >= 2) ret += cnt + cnt - 1 - (flag?1:0); cout << ret << endl; return 0; }
AOJ2297 Rectangular Stamps
問題ページ
Rectangular Stamps | Aizu Online Judge
考えたこと
- 各マスについてempty,R,G,Bの4種類の状態を持ちたい
- これが持てると集合を持ちつつ探索していけそう
- 4^16は無理
- 考察するとそのマスで必要な情報は最終的な色に達しているかどうかの2種類しかない
- 集合の状態が2^16に落ちてこれなら持てる
- BFSで探索
実装がたいへん
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) const int INF = (1LL<<30); char col[] = {'R', 'G', 'B'}; string board[4]; int n, d[1<<16], h[20], w[20]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); cin >> n; REP(i, n) cin >> h[i] >> w[i]; REP(i, 4) cin >> board[i]; REP(i, 1<<16) d[i] = INF; d[0] = 0; queue<int> que; que.push(0); while(que.size()) { int bit = que.front(); que.pop(); if(bit == (1LL<<16)-1) break; // i番目のはんこで左上を(y,x)で色をcとして押す REP(i, n) FOR(y, -h[i]+1, 4) FOR(x, -w[i]+1, 4) REP(c, 3) { int n_bit = bit; FOR(ny, max(0LL, y), min(y+h[i],4LL)) FOR(nx, max(0LL, x), min(x+w[i],4LL)) { // 押した結果同じ色なら1に、違う色なら0に if(board[ny][nx] == col[c]) n_bit |= 1<<(ny*4+nx); else n_bit &= ~(1<<(ny*4+nx)); } if(d[n_bit] == INF) { d[n_bit] = d[bit] + 1; que.push(n_bit); } } } cout << d[(1LL<<16)-1] << endl; return 0; }
AOJ2425 全探索お姉さんの休日
問題ページ
A Holiday of Miss Brute Force | Aizu Online Judge
考えたこと
- 六角形のグリッド上を探索する
- 拡張dijkstraの要領で頂点に時間を増やせばいい気持ちになる
- 時間の上限ないしそのままつけるのは無理
- 時間が影響するのはabs(x*y*t)%6の指示される方向を計算する部分だけ
- 時間はmod 6で持っていても問題なさそう
- d[y][x][t] = (座標y,xに時間tでいるときの最小の指示を無視する回数) として拡張dijkstraをする
- 六角形のグリッドでは位置によってdx,dyが変化するのに注意しつつ実装すると通る
ソースコード
#define __USE_MINGW_ANSI_STDIO 0 #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; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } int dx[] = {0, 1, 1, 0, -1, -1}, dy1[] = {1, 0, -1, -1, -1, 0}, dy2[] = {1, 1, 0, -1, 0, 1}; // d[y][x][t%6] = (ここにたどり着く最小の無視した回数) int d[250][250][6]; int board[250][250]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy; int n; cin >> n; REP(i, n) { int x, y; cin >> x >> y; board[y+100][x+100] = 1; } int lx, ly; cin >> lx >> ly; REP(i, 250) REP(j, 250) REP(k, 6) d[i][j][k] = LLINF; d[100+sy][100+sx][0] = 0; priority_queue<VI, VVI, greater<VI>> que; que.push({d[100+sy][100+sx][0], 100+sy, 100+sx, 0}); while(que.size()) { VI v = que.top(); que.pop(); // cout << v << endl; int x = v[2], y = v[1], t = v[3]; REP(i, 6) { int nx = x + dx[i], ny = y + (x%2==0?dy1:dy2)[i]; if(100-lx <= nx && nx <= 100+lx && 100-ly <= ny && ny <= 100+ly && board[ny][nx]==0) { int tmp = abs((x-100)*(y-100)*t)%6 != i; // cout << i << " " << nx << " " << ny << " " << tmp << endl; if(d[ny][nx][(t+1)%6] > d[y][x][t] + tmp) { d[ny][nx][(t+1)%6] = d[y][x][t] + tmp; que.push({d[ny][nx][(t+1)%6], ny, nx, (t+1)%6}); } } } if(d[y][x][(t+1)%6] > d[y][x][t] + 1) { d[y][x][(t+1)%6] = d[y][x][t] + 1; que.push({d[y][x][(t+1)%6], y, x, (t+1)%6}); } } int ans = LLINF; REP(i, 6) { chmin(ans, d[100+gy][100+gx][i]); // cout << d[100+gy][100+gx][i] << endl; } if(ans==LLINF) cout << -1 << endl; else cout << ans << endl; return 0; }
RUPC2018 day2 J Matrix
解法
ある矩形範囲(a,b,c,d)の最大値はその区間の max(A)*max(B), max(A)*min(B), min(A)*max(B), min(A)*min(B) のうちのどれかとなる。最小値についても同様にどれかになる。
最大値の個数については max(A)*max(B)が最大値であればmax(A)の個数*max(B)の個数, max(A)*min(B)が最大値であればmax(A)の個数*min(B)の個数,… の和によって求められる。
max(A)==min(A)のケースや答えが0になるケースに注意が必要。maxが0のときについて考えると、行列Cの要素のうち+になるようなものが存在してはいけないのでAとBが取る数の符号が異なる場合のみのはずである。したがって (min(A)>=0 かつ max(b)<=0) もしくは (max(A) <= 0 かつ min(B) >= 0) となっているはずで最大値の候補に上げた4個の積のうち0になるものが必ず存在する。つまりans=0のときも値については上に上げた4つのmaxを取ることで求められる。0になる個数を求めるのは矩形範囲全体から0でないものを引くとすればよい。minについても同様。
したがって区間加算区間max,min,countが可能な遅延セグメントツリーを使えばよい。この記事のように抽象化した遅延セグ木でどう実装したのか書く。(最大,最大の個数,最小,最小の個数)がほしいのでTはvector
まとめると遅延セグメントツリーを使いクエリに答えていく。下の実装はdefine int llしてるので注意。
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define PB push_back const ll LLINF = (1LL<<60); // 遅延セグメントツリー template <typename T, typename E> struct segtree { using F = function<T(T,T)>; using G = function<T(T,E)>; using H = function<E(E,E)>; using P = function<E(E,int)>; F f; G g; H h; P p; T d1; E d0; int n; vector<T> dat; vector<E> lazy; segtree(){} segtree(int n_, F f_, G g_, H h_, T d1_, E d0_, P p_=[](E a, int b){return a;}): f(f_), g(g_), h(h_), p(p_), d1(d1_), d0(d0_) { n = 1; while(n < n_) n *= 2; dat.assign(n*2, d1); lazy.assign(n*2, d0); } void build(vector<T> v) { REP(i, v.size()) dat[i+n-1] = v[i]; for(int i=n-2; i>=0; --i) dat[i] = f(dat[i*2+1], dat[i*2+2]); } // 区間の幅がlenの節点kについて遅延評価 inline void eval(int len, int k) { if(lazy[k] == d0) return; if(k*2+1 < n*2-1) { lazy[2*k+1] = h(lazy[k*2+1], lazy[k]); lazy[2*k+2] = h(lazy[k*2+2], lazy[k]); } dat[k] = g(dat[k],p(lazy[k],len)); lazy[k] = d0; } // [a, b) T update(int a, int b, E x, int k, int l, int r) { eval(r-l, k); if(b <= l || r <= a) return dat[k]; if(a <= l && r <= b) { lazy[k] = h(lazy[k], x); return g(dat[k], p(lazy[k],r-l)); } return dat[k] = f(update(a, b, x, 2*k+1, l, (l+r)/2), update(a, b, x, 2*k+2, (l+r)/2, r)); } T update(int a, int b, E x) { return update(a, b, x, 0, 0, n); } // [a, b) T query(int a, int b, int k, int l, int r) { eval(r-l, k); if(a <= l && r <= b) return dat[k]; bool left = !((l+r)/2 <= a || b <= l), right = !(r <= 1 || b <= (l+r)/2); if(left&&right) return f(query(a, b, 2*k+1, l, (l+r)/2), query(a, b, 2*k+2, (l+r)/2, r)); if(left) return query(a, b, 2*k+1, l, (l+r)/2); return query(a, b, 2*k+2, (l+r)/2, r); } T query(int a, int b) { return query(a, b, 0, 0, n); } }; signed main(void) { int H, W, q; scanf("%lld%lld%lld", &H, &W, &q); VI a(H), b(W); REP(i, H) scanf("%lld", &a[i]); REP(i, W) scanf("%lld", &b[i]); // セグ木を定義 auto f = [](VI a, VI b) { // max,minの数 int maxnum = a[0]==max(a[0],b[0])?a[1]:0; maxnum += b[0]==max(a[0],b[0])?b[1]:0; int minnum = a[2]==min(a[2],b[2])?a[3]:0; minnum += b[2]==min(a[2],b[2])?b[3]:0; return VI{ max(a[0],b[0]), maxnum, min(a[2],b[2]), minnum }; }; auto g = [](VI a, int b) { return VI{ a[0]+b, a[1], a[2]+b, a[3] }; }; auto h = [](int a, int b) { return a+b; }; segtree<VI,int> seg1(H, f, g, h, {0,1,0,1}, 0), seg2(W, f, g, h, {0,1,0,1}, 0); // 初期状態を設定 VVI inita, initb; REP(i, H) inita.PB({a[i], 1, a[i], 1}); REP(i, W) initb.PB({b[i], 1, b[i], 1}); seg1.build(inita); seg2.build(initb); // クエリにこたえる REP(i, q) { int type; scanf("%lld", &type); if(type==1) { int a, b, v; scanf("%lld%lld%lld", &a, &b, &v); seg1.update(a-1, b, v); } else if(type==2) { int a, b, v; scanf("%lld%lld%lld", &a, &b, &v); seg2.update(a-1, b, v); } else if(type==4) { int ma = -LLINF, num = 0; int a, b, c, d; scanf("%lld%lld%lld%lld", &a, &b, &c, &d); VI v1 = seg1.query(a-1, b); VI v2 = seg2.query(c-1, d); ma = max({ v1[0]*v2[0], v1[2]*v2[2], v1[0]*v2[2], v1[2]*v2[0] }); // maxが0のケース if(ma == 0) { int tmpa = 0, tmpb = 0; if(v1[0] == 0) tmpa = v1[1]; if(v1[2] == 0) tmpa = v1[3]; if(v2[0] == 0) tmpb = v2[1]; if(v2[2] == 0) tmpb = v2[3]; num = (b-a+1)*(d-c+1) - (b-a+1-tmpa)*(d-c+1-tmpb); } else { if(v1[0] == v1[2] && v2[0] == v2[2]) { num = (b-a+1) * (d-c+1); } else if(v1[0] == v1[2] || v2[0] == v2[2]) { if(v1[2]*v2[2] == ma) num += v1[3]*v2[3]; if(v1[0]*v2[0] == ma) num += v1[1]*v2[1]; } else { if(v1[0]*v2[0] == ma) num += v1[1]*v2[1]; if(v1[0]*v2[2] == ma) num += v1[1]*v2[3]; if(v1[2]*v2[0] == ma) num += v1[3]*v2[1]; if(v1[2]*v2[2] == ma) num += v1[3]*v2[3]; } } printf("%lld %lld\n", ma, num); } else if(type==3) { int mi = LLINF, num = 0; int a, b, c, d; scanf("%lld%lld%lld%lld", &a, &b, &c, &d); VI v1 = seg1.query(a-1, b); VI v2 = seg2.query(c-1, d); mi = min({ v1[0]*v2[0], v1[2]*v2[2], v1[0]*v2[2], v1[2]*v2[0] }); // minが0の場合 if(mi == 0) { int tmpa = 0, tmpb = 0; if(v1[0] == 0) tmpa = v1[1]; if(v1[2] == 0) tmpa = v1[3]; if(v2[0] == 0) tmpb = v2[1]; if(v2[2] == 0) tmpb = v2[3]; num = (b-a+1)*(d-c+1) - (b-a+1-tmpa)*(d-c+1-tmpb); } else { if(v1[0] == v1[2] && v2[0] == v2[2]) { num = (b-a+1) * (d-c+1); } else if(v1[0] == v1[2] || v2[0] == v2[2]) { if(v1[2]*v2[2] == mi) num += v1[3]*v2[3]; if(v1[0]*v2[0] == mi) num += v1[1]*v2[1]; } else { if(v1[0]*v2[0] == mi) num += v1[1]*v2[1]; if(v1[0]*v2[2] == mi) num += v1[1]*v2[3]; if(v1[2]*v2[0] == mi) num += v1[3]*v2[1]; if(v1[2]*v2[2] == mi) num += v1[3]*v2[3]; } } printf("%lld %lld\n", mi, num); } } return 0; }
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; }