非常明显的二分图模型,将不同的三角形视为左右部,白格子视为边,流量意义为白格子填的数。
对左右部限制点权,意义为每个三角形需要填的数。
对每个三角形权值减去他所拥有的白格子个数,限制白格子下界1。
每个白格子连接他所贡献的两个三角形格子,容量设为8。
题目保证有解,最大流必是满流,对链表添加一组额外的域表示白格子坐标,遍历所有边,如果两端点分别位于左右部,则这条边是白格子,将流量填入坐标即可,记得$+1$。
#include <iostream>
#include <cstring>
#define x first
#define y second
using namespace std;
const int K = 110, N = 10010, M = 100010;
const int INF = 0x3f3f3f3f;
using PII = pair<int, int>;
int e[M], ne[M], f[M], h[N], idx;
int x[M], y[M];
int q[N], cur[N], d[N];
int n, m, S, T;
int g[K][K];
PII id[K][K], bel[K][K];
int val1[N], val2[N];
void insert(int u, int v, int d, int i = 0, int j = 0) {
e[idx] = v, ne[idx] = h[u], f[idx] = d, x[idx] = i, y[idx] = j, h[u] = idx++;
e[idx] = u, ne[idx] = h[v], f[idx] = 0, h[v] = idx++;
}
bool bfs() {
memset(d, -1, sizeof d);
int tt = -1, hh = 0;
q[++tt] = S, cur[S] = h[S], d[S] = 0;
while (hh <= tt) {
int t = q[hh++];
for (int i = h[t]; ~i; i = ne[i]) {
int j = e[i];
if (d[j] == -1 && f[i]) {
cur[j] = h[j];
d[j] = d[t] + 1;
if (j == T) return true;
q[++tt] = j;
}
}
}
return false;
}
int find(int u, int limit) {
if (u == T) return limit;
int flow = 0;
for (int i = cur[u]; ~i && flow < limit; i = ne[i]) {
int j = e[i];
cur[u] = i;
if (d[j] == d[u] + 1 && f[i]) {
int t = find(j, min(f[i], limit - flow));
if (!t) d[j] = -1;
f[i] -= t, f[i ^ 1] += t, flow += t;
}
}
return flow;
}
int dinic() {
int r = 0, flow;
while (bfs()) while (flow = find(S, INF)) r += flow;
return r;
}
int main() {
cin.tie(0)->sync_with_stdio(false);
S = N - 1, T = S - 1;
while (cin >> n >> m) {
int cnt1 = 0, cnt2 = 0;
memset(id, 0, sizeof id);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
string s;
cin >> s;
if (s == ".......") {
id[i][j] = {-1, -1};
continue;
}
if (s[6] != 'X') {
val2[++cnt2] = stoi(s.substr(4, 3));
id[i][j].y = cnt2;
}
if (s[0] != 'X') {
val1[++cnt1] = stoi(s.substr(0, 3));
id[i][j].x = cnt1;
}
}
}
memset(h, -1, sizeof h), idx = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (~id[i][j].x) continue;
auto& [t, o] = bel[i][j];
if (!~id[i - 1][j].x) val1[t = bel[i - 1][j].x]--;
else val1[t = id[i - 1][j].x]--;
if (!~id[i][j - 1].y) val2[o = bel[i][j - 1].y]--;
else val2[o = id[i][j - 1].y]--;
}
}
for (int i = 1; i <= cnt1; i++) insert(S, i, val1[i]);
for (int i = 1; i <= cnt2; i++) insert(i + cnt1, T, val2[i]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (id[i][j].x == -1) {
auto& [a, b] = bel[i][j];
insert(a, b + cnt1, 8, i, j);
}
}
}
dinic();
for (int i = 0; i < idx; i += 2) {
int from = e[i ^ 1], to = e[i];
if (from <= cnt1 && to > cnt1 && to <= cnt1 + cnt2) {
g[x[i]][y[i]] = f[i ^ 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (~id[i][j].x) cout << "_ ";
else cout << g[i][j] + 1 << ' ';
}
cout << '\n';
}
}
return 0;
}