题目链接:https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=0&problem=2023&mosmsg=Submission+received+with+ID+26557955
建立一个二分图,每行对应一个 \(X\) 结点,每列对应一个 \(Y\) 结点,从 \(s\) 向 \(X_I\) 连容量为 \(r[i] - C\),从 \(Y_i\) 向 \(t\) 连容量为 \(c[i] - R\),
每个结点 (X_i,Y_j), 从 \(X_i\) 向 \(Y_j\) 连容量为 \(19\),最大流每条边对应的流量就是矩阵的元素大小
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 405;
const int INF = 1000000007;
int T, n, m, ans;
int R[maxn], C[maxn], r[maxn], c[maxn];
int id[maxn][maxn];
int h[maxn], cnt = 1;
struct E{
int to, next, cap;
}e[maxn << 1];
void add(int u, int v, int c){
e[++cnt].to = v;
e[cnt].cap = c;
e[cnt].next = h[u];
h[u] = cnt;
}
int d[maxn];
queue<int> q;
int s, t;
int bfs(){
while(!q.empty()) q.pop();
memset(d,0,sizeof(d));
d[s] = 1;
q.push(s);
while(!q.empty()){
int u = q.front(); q.pop();
for(int i = h[u] ; i != -1 ; i = e[i].next){
int v = e[i].to;
if(!d[v] && e[i].cap){
d[v] = d[u] + 1;
q.push(v);
}
}
}
return d[t];
}
int dfs(int u,int lim){
if(u==t) return lim;
int f=0,tmp;
for(int i=h[u];i!=-1;i=e[i].next){
int v=e[i].to;
if(d[v]==d[u]+1&&e[i].cap&&(tmp=dfs(v,min(lim,e[i].cap)))){
e[i].cap-=tmp; e[i^1].cap+=tmp;
f+=tmp; lim-=tmp;
if(!lim) return f;
}
}
if(lim) d[u]=0;
return f;
}
void dinic(){
ans=0;
while(bfs()){
ans+=dfs(s, INF);
}
}
ll read(){ ll s = 0, f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); } return s * f; }
int main(){
int kase = 0;
T = read();
while(T--){
memset(h, -1, sizeof(h)); cnt = 1;
n = read(), m = read();
for(int i = 1 ; i <= n ; ++i){
R[i] = read();
}
for(int i = 1 ; i <= n ; ++i){
r[i] = R[i] - R[i - 1];
}
for(int i = 1 ; i <= m ; ++i){
C[i] = read();
}
for(int i = 1 ; i <= m ; ++i){
c[i] = C[i] - C[i - 1];
}
s = n + m + 1, t = n + m + 2;
for(int i = 1 ; i <= n ; ++i){ // 源点 -> 行
add(s, i, r[i] - m);
add(i, s, 0);
}
for(int i = 1 ; i <= m ; ++i){ // 列 -> 汇点
add(n + i, t, c[i] - n);
add(t, n + 1, 0);
}
for(int i = 1 ; i <= n ; ++i){ // (i,j)
for(int j = 1 ; j <= m ; ++j){
add(i, n + j, 19);
id[i][j] = cnt;
add(n + j, i, 0);
}
}
// for(int i = 1 ; i <= n ; ++i){ // (i,j)
// for(int j = 1 ; j <= m ; ++j){
// printf("%d ", id[i][j]);
// } printf("\n");
// }
dinic();
printf("Matrix %d\n", ++kase);
for(int i = 1 ; i <= n ; ++i){
for(int j = 1 ; j <= m ; ++j){
printf("%d ", 19 - e[id[i][j]].cap + 1);
} printf("\n");
}
}
return 0;
}