网络流不难写，难的建一个能解决问题的模型。。
即使我知道这是网络流专题的题目，也绝不会能想出这种解法，=_=||
题意：
给出一个矩阵的 前i行和 以及 前i列和，然后找到一个满足要求的矩阵，而且每个元素在1~20之间。
分析：
先求出每行的元素和A'i 每列的元素和B'i
紫书上说建一个二分图，每行是一个X节点，每列代表一个Y节点。
因为流量最小是0，而题中说元素大小在1~20之间，所以我们先将每个元素都减一。
这样每行的元素和就变成了A'i-C，每列之和变为B'i-R
XY之间每条边的容量为19
源点到X中每个点的容量为A'i-C，Y中的每个点到汇点的容量为B'i-R。当所有从源点出发和在汇点结束的边满载时有解。
“为什么这样做是对的呢？请读者思考。”
好吧，那我就思考。Xi->Yj这条边就对应矩阵中第i行第j列元素的值，而且所有从X出发的边，汇聚到Yj的总流量就是第j列的和。
反过来，从Xi出发的总流量就是第i行的和，分流到各个Y中。
#include <bits/stdc++.h> using namespace std; const int maxn = + ;
const int INF = ; struct Edge
{
int from, to, cap, flow;
Edge(int u=, int v=, int c=, int f=): from(u), to(v), cap(c), flow(f) {}
}; struct EdmondsKarp
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
int a[maxn];
int p[maxn]; void Init(int n)
{
for(int i = ; i < n; ++i) G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int cap)
{
edges.push_back(Edge(from, to, cap, ));
edges.push_back(Edge(to, from, , ));
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
} int MaxFlow(int s, int t)
{
int flow = ;
for(;;)
{
memset(a, , sizeof(a));
queue<int> Q;
Q.push(s);
a[s] = INF;
while(!Q.empty())
{
int x = Q.front(); Q.pop();
for(int i = ; i < G[x].size(); ++i)
{
Edge& e = edges[G[x][i]];
if(!a[e.to] && e.cap > e.flow)
{
a[e.to] = min(a[x], e.cap - e.flow);
p[e.to] = G[x][i];
Q.push(e.to);
}
}
if(a[t]) break;
}
if(!a[t]) break;
for(int u = t; u != s; u = edges[p[u]].from)
{
edges[p[u]].flow += a[t];
edges[p[u]^].flow -= a[t];
}
flow += a[t];
}
return flow;
}
}; EdmondsKarp g;
int ind[maxn][maxn];//ind[i][j]记录第i行第j列对应的边的编号 int main()
{
//freopen("in.txt", "r", stdin); int T, R, C;
scanf("%d", &T);
for(int kase = ; kase <= T; ++kase)
{
scanf("%d%d", &R, &C);
g.Init(R+C+);
int cur, last = ;
for(int i = ; i <= R; ++i)
{//第i行的节点标号为i，源点标号为0
scanf("%d", &cur);
g.AddEdge(, i, cur - last - C);
last = cur;
}
last = ;
for(int i = ; i <= C; ++i)
{//第i列的标号为R+i，汇点标号为R+C+1
scanf("%d", &cur);
g.AddEdge(R+i, R+C+, cur - last - R);
last = cur;
}
for(int i = ; i <= R; ++i)
for(int j = ; j <= C; ++j)
{
g.AddEdge(i, j+R, );
ind[i][j] = g.edges.size() - ;//因为AddEdge中还有一条反向边,所以是-2
}
g.MaxFlow(, R+C+); printf("Matrix %d\n", kase);
for(int i = ; i <= R; ++i)
{
printf("%d", g.edges[ind[i][]].flow + );
for(int j = ; j <= C; ++j)
printf(" %d", g.edges[ind[i][j]].flow + );
printf("\n");
}
printf("\n");
} return ;
}
代码君