1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
| #include <bits/stdc++.h> #define R(i, r) for (int i = 0; i < (r); ++i) #define rep(i, l, r) for (int i = (l); i <= (r); ++i) #define per(i, l, r) for (int i = (l); i >= (r); --i) using std::cerr; using std::cin; using std::cout; using std::endl; using std::make_pair; using std::pair; typedef pair<int, int> pii; typedef long long ll; typedef unsigned int ui; typedef unsigned long long ull; const int K = 15, N = 5010; int n[K]; ll a[K][N], sig[K]; std::map<ll, pii> s; pii g[K][N]; int clr[K][N]; int f[1<<K], from[1<<K]; pii plan[1<<K]; int origin[1<<K]; pii out[K]; void dfs(int state){ if (origin[state]){ int x = plan[state].first, y = plan[state].second; pii n; do { n = g[x][y]; out[n.first] = {a[n.first][n.second], x}; x = n.first, y = n.second; } while(x != plan[state].first); } else { dfs(from[state]); dfs(state^from[state]); } } int main() { #ifdef LOCAL freopen("input", "r", stdin); #endif std::ios::sync_with_stdio(0); cout.tie(0); int k; cin >> k; ll avg = 0; R(i, k){ cin >> n[i]; R(j, n[i]){ cin >> a[i][j]; sig[i] += a[i][j]; s[a[i][j]] = {i,j}; } avg += sig[i]; } if (avg % k != 0){ cout << "No"; return 0; } avg /= k; R(i, k) R(j, n[i]){ ll x = avg - sig[i] + a[i][j]; if (s.count(x)) g[i][j] = s[x]; else g[i][j].first = -1; } int x, y, state, flag; pii np; int cnt = 0; R(i, k) R(j, n[i]){ if (clr[i][j]) continue; x = i, y = j; clr[x][y] = ++cnt; while(g[x][y].first != -1){ np = g[x][y]; x = np.first, y = np.second; if (clr[x][y] == cnt){ state = 0, flag = 1; int ox = x, oy = y; do { if (state&(1<<x)) { flag = 0; break; } state |= (1<<x); np = g[x][y]; x = np.first, y = np.second; } while(x != ox || y != oy); if (flag) f[state] = origin[state] = 1, plan[state] = {x, y}; break; } else if (clr[x][y] != 0) break; clr[x][y] = cnt; } } f[0] = 1; for(int i = 1; i < (1<<k); ++i){ for(int j = i; j && !f[i]; j = ((j-1)&i)){ if (f[j] && f[i^j]){ f[i] = 1; from[i] = j; } } } if(!f[(1<<k)-1]){ cout << "No"; return 0; } cout << "Yes\n"; dfs((1<<k)-1); R(i, k){ cout << out[i].first << ' ' << out[i].second+1 << endl; } return 0; }
|