传送门：https://jzoj.net/senior/#main/show/2701
【题目大意】
给出矩阵A，求矩阵B，使得
最小，矩阵B每个元素在[L,R]内
n<=200,1<=Aij,L,R<=1000, L<=R
【题解】
我们二分答案x，然后对行列建点，每行向每列连[L,R]的边，然后S向每行连[max(S[i]-x), S[i]+x]的边，每列向T连[max(T[i]-x), T[i]+x]的边，判断是否有可行流即可。
其中S[i]表示A中第i行的和，T[i]表示A中第i列的和。
判断有源汇上下界可行流：按照无源汇那样建边，多来一条(T->S，[0,inf])即可。
然后跑dinic，判断从SS流出的边是否全流满。
# include <queue> # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 200 + 10, N = 5e5 + 10, inf = 1e9; const int mod = 1e9+7; # define RG register # define ST static int n, m, a[M][M], s1[M], s2[M], S, T, L, R; int head[M * 4], nxt[N], to[N], flow[N], tot, indeg[M * 4]; inline void add(int u, int v, int fl) { ++tot; nxt[tot] = head[u]; head[u] = tot; to[tot] = v; flow[tot] = fl; } inline void adde(int u, int v, int fl) { add(u, v, fl), add(v, u, 0); } inline void tadd(int u, int v, int lf, int rf) { adde(u, v, rf-lf); indeg[v] += lf; indeg[u] -= lf; } namespace MF { queue<int> q; int c[M * 3], cur[M * 3]; inline bool bfs() { for (int i=1; i<=n+m+4; ++i) c[i] = -1; while(!q.empty()) q.pop(); q.push(S); c[S] = 1; while(!q.empty()) { int top = q.front(); q.pop(); for (int i=head[top]; i; i=nxt[i]) { if(c[to[i]] != -1 || flow[i] == 0) continue; c[to[i]] = c[top] + 1; q.push(to[i]); if(to[i] == T) return 1; } } return 0; } inline int dfs(int x, int low) { if(x == T) return low; int r = low, fl; for (int i=cur[x]; i; i=nxt[i]) { if(c[to[i]] != c[x]+1 || flow[i] == 0) continue; fl = dfs(to[i], min(r, flow[i])); flow[i] -= fl; flow[i^1] += fl; r -= fl; if(flow[i] > 0) cur[x] = i; if(!r) return low; } if(r == low) c[x] = -1; return low-r; } inline int main() { int ans = 0; while(bfs()) { for (int i=1; i<=n+m+4; ++i) cur[i] = head[i]; ans += dfs(S, inf); } return ans; } } # define line(x) (x) # define row(x) (x+n) inline void build(int x) { int SS = n+m+1, TT = n+m+2; S = n+m+3, T = n+m+4; for (int i=1; i<=n+m+2; ++i) indeg[i] = 0; for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j) tadd(line(i), row(j), L, R); for (int i=1; i<=n; ++i) tadd(SS, line(i), max(0, s1[i]-x), s1[i]+x); for (int i=1; i<=m; ++i) tadd(row(i), TT, max(0, s2[i]-x), s2[i]+x); tadd(TT, SS, 0, inf); for (int i=1; i<=n+m+2; ++i) { if(indeg[i] < 0) adde(i, T, -indeg[i]); else adde(S, i, indeg[i]); } } inline bool chk(int x) { tot = 1; memset(head, 0, sizeof head); build(x); MF::main(); // cout << x << endl; for (int i=head[S]; i; i=nxt[i]) { // cout << flow[i] << ' '; if(flow[i] != 0) { // cout << endl; return false; } } // cout << endl; return true; } inline void gans(int ans) { for (int i=1; i<=n; ++i, puts("")) { for (int j=1; j<=m; ++j) { for (int p=head[line(i)]; p; p=nxt[p]) { if(to[p] == row(j)) { printf("%d ", flow[p^1] + L); break; } } } } } int main() { freopen("mat.in", "r", stdin); freopen("mat.out", "w", stdout); cin >> n >> m; for (int i=1; i<=n; ++i) for (int j=1; j<=m; ++j) { scanf("%d", &a[i][j]); s1[i] += a[i][j]; s2[j] += a[i][j]; } cin >> L >> R; int l = 0, r = 2e5, mid, ans = 0; while(1) { if(r-l <= 3) { for (int i=l; i<=r; ++i) if(chk(i)) { ans = i; break; } break; } mid = l+r>>1; if(chk(mid)) r = mid; else l = mid; } cout << ans << endl; gans(ans); return 0; }