考虑转化成匹配问题。
对每行建点 \(p_i\),每个数建点 \(q_i\),\(\forall i \in [1, n], j \in [1, m]\),连边 \((p_i, q_{a_{i, j}})\),问题转化成求这个二分图能否恰好被分解成 \(m\) 组完美匹配以及方案。
直接给出做法:每次任意找出一组完美匹配,并把边从图中删除,做 \(m\) 次。若有一次找不出完美匹配就无解。
为什么是对的呢?
考虑 Hall 定理。二分图有完美匹配的充要条件是,对于左部点集的任意一个子集 \(S\),它的邻居集合 \(N(S)\)(可重集)均满足 \(|S| \ge |N(S)|\)。
Hall 定理是可以推广的,二分图有 \(m\) 组完美匹配的充要条件是,对于左部点集的任意一个子集 \(S\),它的邻居集合 \(N(S)\) 均满足 \(m|S| \ge |N(S)|\)。
如果原图满足这个条件,那么随便删除一组完美匹配后也依然满足。如果原图不满足这个条件,那么它就找不出来 \(m\) 组完美匹配。
使用 Dinic 求二分图匹配,复杂度 \(O(n^{1.5}m^2)\)。
code
// Problem: G - Rearranging
// Contest: AtCoder - GAMEFREAK Programming Contest 2023 (AtCoder Beginner Contest 317)
// URL: https://atcoder.jp/contests/abc317/tasks/abc317_g
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mkp make_pair
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 110;
const int maxm = 1000000;
const int inf = 0x3f3f3f3f;
int n, m, tot, a[maxn][maxn], b[maxn][maxn], c[maxn][maxn];
int id1[maxn], id2[maxn], ntot, head[maxm], len = 1, S, T;
vector<int> vc[maxn][maxn];
struct E {
int u, v, d;
E(int a = 0, int b = 0, int c = 0) : u(a), v(b), d(c) {}
} G[maxm];
struct edge {
int to, next, cap, flow, id;
} edges[maxm];
inline void add_edge(int u, int v, int c, int f, int id) {
edges[++len].to = v;
edges[len].next = head[u];
edges[len].cap = c;
edges[len].flow = f;
edges[len].id = id;
head[u] = len;
}
struct Dinic {
int d[maxm], cur[maxm];
bool vis[maxm];
inline void add(int u, int v, int c, int id) {
add_edge(u, v, c, 0, id);
add_edge(v, u, 0, 0, id);
}
inline bool bfs() {
for (int i = 1; i <= ntot; ++i) {
vis[i] = 0;
d[i] = -1;
}
queue<int> q;
vis[S] = 1;
d[S] = 0;
q.push(S);
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[u] + 1;
q.push(e.to);
}
}
}
return vis[T];
}
int dfs(int u, int a) {
if (u == T || !a) {
return a;
}
int flow = 0, f;
for (int &i = cur[u]; i; i = edges[i].next) {
edge &e = edges[i];
if (d[e.to] == d[u] + 1 && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[i ^ 1].flow -= f;
flow += f;
a -= f;
if (!a) {
break;
}
}
}
return flow;
}
inline int solve() {
int flow = 0;
while (bfs()) {
for (int i = 1; i <= ntot; ++i) {
cur[i] = head[i];
}
flow += dfs(S, inf);
}
return flow;
}
} solver;
void solve() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
id1[i] = ++ntot;
for (int j = 1; j <= m; ++j) {
scanf("%d", &a[i][j]);
++c[i][a[i][j]];
}
}
for (int i = 1; i <= n; ++i) {
id2[i] = ++ntot;
}
S = ++ntot;
T = ++ntot;
for (int i = 1; i <= n; ++i) {
G[++tot] = E(S, id1[i], 1);
G[++tot] = E(id2[i], T, 1);
for (int j = 1; j <= n; ++j) {
for (int _ = 0; _ < c[i][j]; ++_) {
G[++tot] = E(id1[i], id2[j], 1);
}
}
}
for (int p = 1; p <= m; ++p) {
len = 1;
mems(head, 0);
for (int i = 1; i <= tot; ++i) {
int u = G[i].u, v = G[i].v, d = G[i].d;
solver.add(u, v, d, i);
}
if (solver.solve() != n) {
puts("No");
return;
}
for (int i = head[S]; i; i = edges[i].next) {
edge e1 = edges[i];
if (!(i & 1) && e1.flow) {
for (int j = head[e1.to]; j; j = edges[j].next) {
edge e2 = edges[j];
if (!(j & 1) && e2.flow) {
int id = e2.id;
--G[id].d;
int x = e1.to, w = e2.to - n;
b[x][p] = w;
}
}
}
}
}
puts("Yes");
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
printf("%d ", b[i][j]);
}
putchar('\n');
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}
- Rearranging Beginner AtCoder Contest 317beginner atcoder contest 317 rearranging beginner atcoder contest contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 328 beginner atcoder contest 334 beginner atcoder contest 332