题意是已知一个矩阵的行数和列数和前i行的和还有前j列的和, 矩阵每个元素的值都介于1~20要求构造出这个矩阵,将每一行看成一个点, 每一列看成一个点, 源点和行相连容量为该行的和, 每个列的点和汇点相连容量为该列的和, 每个行和每个列也相连容量为20, 行和列形成一个完全二分图的结构, 对应的行连到对应的列的流量即为该行该列的数值, 由于每个数要大于1所以实现时每条弧的容量还要减去某一个值,
详见代码。
#include <iostream> #include <string> #include <cmath> #include <cstdio> #include <cstring> #include <cstdlib> #include <ctime> #include <queue> #include <stack> #include <list> #include <algorithm> using namespace std; const int N = 505; const int M = 12005; const int INF = 1000000000; int res[N][N]; typedef int LL; struct Dinic { struct Edge { int v; LL cap, flow; Edge* next, * pair; void init(int a, LL b, Edge* e1, Edge* e2) { v = a, cap = b, flow = 0, next = e1, pair = e2; } }; Edge* head[N], * used[N]; Edge* it; int lev[N], que[N]; Edge E[M]; int n, s, t; LL maxFlow; void init(int n, int s, int t) { it = E; this->n = n; this->s = s, this->t = t; for (int i = 0; i < n; i++) head[i] = 0; } void add(int u, int v, LL c) { it->init(v, c, head[u], it + 1); head[u] = it++; it->init(u, 0, head[v], it - 1); head[v] = it++; } bool bfs() { for (int i = 0; i < n; lev[i++] = -1); lev[s] = 0; int st = 0, ed = 0; que[ed++] = s; while (st < ed) { int u = que[st++]; for (Edge* e = head[u]; e; e = e->next) { int v = e->v; if (lev[v] == -1 && e->cap > e->flow) { lev[v] = lev[u] + 1; que[ed++] = v; } } } return lev[t] != -1; } LL dfs(int u, LL f) { if (u == t) return f; for (Edge* & e = used[u]; e; e = e->next) { int v = e->v; if (e->cap > e->flow && lev[v] == lev[u] + 1) { LL tmp = dfs(v, min(e->cap - e->flow, f)); if (tmp > 0) { e->flow += tmp; e->pair->flow -= tmp; return tmp; } } } return 0; } void run() { maxFlow = 0; while (bfs()) { for (int i = 0; i < n; i++) used[i] = head[i]; LL f = 1; while (f) { f = dfs(s, INF); maxFlow += f; } } } void solve(int r) { for (int u = 1; u <= r; u++) { for (Edge* e = head[u]; e; e = e->next) { if (e->v > r) { res[u][e->v - r] = e->flow + 1; } } } } }G; int main() { int i,j, r, c; int T; scanf("%d",&T); int test=0; while(T--) { scanf("%d %d",&r,&c); int s,t; s=0,t=r+c+1; G.init(t + 1, s, t); int pre=0; for(i=1; i<=r; i++) { int temp; scanf("%d",&temp); G.add(s,i,temp-pre-c); for(j=1; j<=c; j++) { G.add(i,r+j,19); } pre=temp; } pre=0; for(i=1; i<=c; i++) { int temp; scanf("%d",&temp); G.add(r+i,t,temp-pre-r); pre=temp; } printf("Matrix %d\n",++test); G.run(); G.solve(r); for (i = 1; i <= r; i++) { for (j = 1; j <= c - 1; j++) printf("%d ", res[i][j]); printf("%d\n", res[i][c]); } puts(""); } return 0; }