Untitled
#include "bits/stdc++.h" using namespace std; #ifdef LOCAL #include "debug.h" #else #define debug(x...) #endif using ll = long long; constexpr int N = 2e5; constexpr int K = 7; constexpr int M = 2187; int n, k; int a[K][N]; vector<int> ids[M]; bool match(int am, int bm) { for (int i = 0; i < k; i++) { if (am % 3 == bm % 3 && am % 3 != 2) return false; am /= 3; bm /= 3; } return true; } struct edge { int v, c, f, id; }; vector<edge> g[M + 2]; void addEdge(int u, int v, int st) { g[u].emplace_back(v, st, 0, (int)g[v].size()); g[v].emplace_back(u, 0, 0, (int)g[u].size() - 1); } int d[M + 2]; bool bfs() { fill(d, d + M + 2, -1); queue<int> q; q.push(M); d[M] = 0; while (!q.empty()) { int t = q.front(); q.pop(); if (t == M + 1) return true; for (auto &[v, c, f, id] : g[t]) { if (c - f > 0 && d[v] == -1) { d[v] = d[t] + 1; q.push(v); } } } return false; } int ptr[M + 2]; int dfs(int u, int flow) { if (!flow) return 0; if (u == M + 1) return flow; for (int &to = ptr[u]; to < (int)g[u].size(); to++) { if (d[g[u][to].v] != d[u] + 1) continue; int pushed = dfs(g[u][to].v, min(flow, g[u][to].c - g[u][to].f)); if (pushed) { g[u][to].f += pushed; g[g[u][to].v][g[u][to].id].f -= pushed; return pushed; } } return 0; } int dinic() { int flow = 0; while (bfs()) { fill(ptr, ptr + M + 2, 0); while (int pushed = dfs(M, INT_MAX)) { flow += pushed; } } return flow; } void test_case() { cin >> n >> k; for (int j = 0; j < n; j++) { for (int i = 0; i < k; i++) { cin >> a[i][j]; } } for (int i = 0; i < k; i++) { int tmp[n]; copy(a[i], a[i] + n, tmp); sort(tmp, tmp + n); int median = (tmp[n / 2 - 1] + tmp[n / 2]) / 2; int half = (tmp[n / 2 - 1] + tmp[n / 2]) % 2; for (int j = 0; j < n; j++) { if (a[i][j] > median + half) { a[i][j] = 1; } else if (a[i][j] < median) { a[i][j] = 0; } else { a[i][j] = 2; } } } for (int i = 0; i < n; i++) { int val = 0, mult = 1; for (int j = k - 1; j >= 0; j--) { val += a[j][i] * mult; mult *= 3; } ids[val].push_back(i); } int MX = 1; for (int i = 0; i < k; i++) { MX *= 3; } for (int am = 0; am < MX / 3; am++) { addEdge(M, am, ids[am].size()); } for (int bm = MX / 3; bm < MX; bm++) { addEdge(bm, M + 1, ids[bm].size()); } for (int am = 0; am < MX / 3; am++) { for (int bm = MX / 3; bm < MX; bm++) { if (match(am, bm)) { addEdge(am, bm, min(ids[am].size(), ids[bm].size())); } } } if (dinic() == n / 2) { cout << "YES\n"; for (int u = 0; u < MX / 3; u++) { for (auto &[v, c, f, id] : g[u]) { while (f-- > 0) { cout << ids[u].back() + 1 << ' ' << ids[v].back() + 1 << '\n'; ids[u].pop_back(); ids[v].pop_back(); } } } } else { cout << "NO\n"; } } signed main() { ios::sync_with_stdio(false); cin.tie(NULL); int tests = 1; // cin >> tests; while (tests--) { test_case(); } return 0; }
Leave a Comment