[ABC317G] Rearranging 题解

标签：二分 head idx int 题解 ABC317G aligned Rearranging

取自我的洛谷博客：https://www.luogu.com.cn/blog/SunnyYuan/solution-at-abc317-g

借鉴了官方题解思路。

思路

首先我们要建立一个二分图。

对于输入的 \(a_{i, j}\)，我们可以连接 左侧的 \(i\) 和 右侧的 \(a_{i, j}\)。

比如样例 \(1\)：

注意：左边的 \(1, 2, 3\) 和 右边的 \(1, 2, 3\) 完全不一样，一个是行数，一个是数字。

1. 那我们现在找出一组二分图的最大匹配，那么就代表对于固定的一列，第 \(i\) 行的数字就可以确定了。

   比如上图中橙色的边，它们就是一组二分图的最大匹配，我们可以通过其知道对于一列，可以这么填：

\[\begin{aligned} 1\\ 3\\ 2\\ \end{aligned} \]

2. 我们将已经匹配的边删去，然后再跑下一次的二分图，构建下一列的数字。就这样执行 \(m\) 遍，就可以做出答案。

   

   可以得到最大匹配，然后构建出这一列数字：

\[\begin{aligned} 1\\ 2\\ 3\\ \end{aligned} \]

3. 最后将这么多列数字按任意顺序输出就可以了。

\[\begin{aligned} \text{1 1}\\ \text{2 3}\\ \text{3 2}\\ \end{aligned} \]

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 210, M = 40010, INF = 0x3f3f3f3f;

struct edge {
	int to, next, w;
} e[M];

int head[N], idx = 1;

void add(int u, int v, int w) {
	idx++, e[idx].to = v, e[idx].next = head[u], e[idx].w = w, head[u] = idx;
	idx++, e[idx].to = u, e[idx].next = head[v], e[idx].w = 0, head[v] = idx;
}

int S, T;
int n, m;
int q[N], hh, tt;
int d[N];
int ans[N][N];

bool bfs() {
	memset(d, 0, sizeof(d));
	hh = tt = 0;
	q[0] = S;
	d[S] = 1;

	while (hh <= tt) {
		int u = q[hh++];

		for (int i = head[u]; i; i = e[i].next) {
			int to = e[i].to;
			if ((!d[to]) && e[i].w) {
				d[to] = d[u] + 1;
				q[++tt] = to;
			}
		}
	}

	return d[T];
}

int dinic(int u, int limit) {
	if (u == T) return limit;

	int rest = limit;
	for (int i = head[u]; i && rest; i = e[i].next) {
		int to = e[i].to;
		if (d[to] == d[u] + 1 && e[i].w) {
			int k = dinic(to, min(rest, e[i].w));
			if (!k) d[to] = INF;
			rest -= k;
			e[i].w -= k;
			e[i ^ 1].w += k;
		}
	}
	return limit - rest;
}

int maxflow() {
	int ans = 0, flow = 0;
	while (bfs()) while (flow = dinic(S, INF)) ans += flow;
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m;
	S = 0, T = n << 1 | 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			int x;
			cin >> x;
			add(i, x + n, 1);
		}
	}
	int tmp = idx;
	for (int i = 1; i <= n; i++) add(S, i, 1), add(i + n, T, 1);

	for (int j = 1; j <= m; j++) {
		if (maxflow() != n) {
			cout << "No\n";
			return 0;
		}
		for (int i = 3; i <= tmp; i += 2) if (e[i].w == 1) {
			int u = e[i].to, v = e[i ^ 1].to;
			ans[u][j] = v - n;
			e[i].w = e[i ^ 1].w = 0;
		}
		for (int i = tmp + 2; i <= idx; i += 2) {
			if (e[i].w == 1) {
				e[i ^ 1].w = 1;
				e[i].w = 0;
			}
		}
	}
	cout << "Yes\n";
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}
	return 0;
}

标签：二分,head,idx,int,题解,ABC317G,aligned,Rearranging
From： https://www.cnblogs.com/Yuan-Jiawei/p/17660224.html