UVA11082 - Matrix Decompressing (上下界网络流)

Description

UVA11082 - Matrix Decompressing Some RxC matrix of positive integers is encoded and represented by its R cumulative row sum and C column sum entries. Given, R, C and those R+C cumulative row sum and column sums, you want to decode the matrix (i.e., find all the individual R * C entries).

In other words, the i-th row sum is the sum of all the entries in row i. And the cumulative i-th row sum is the sum of all the row sums from row 1 to row i (inclusive).

Input

There can be multiple test cases. The first line of input contains the number of test cases, T (1 ≤T ≤ 100). Each test case contains 3 lines of input. The first line of the test case gives the size of the matrix: the number of rows, R (1 ≤ R ≤ 20) and the number of columns C (1 ≤ C ≤20). The next line contains all the R cumulative row sums, and the last line of the test case contains the C cumulative column sums. Any two successive numbers in the same line is separated by a single space.

Output

For each test case print the label of the test case in the first line. The format of this label should be “Matrix x” where x would be replaced by the serial number of the test case starting at 1. In each of the following R lines print C integers giving all the individual entries of the matrix. You can assume that there is at least one solution for each of the given encodings. To simplify the problem further, we add the constraint that each entry in the matrix must be an integer between 1 and 20. In case of multiple solutions, you can output any one of them.

Sample Input

2
3 4
10 31 58
10 20 37 58
3 4
10 31 58
10 20 37 58

Sample Output

Matrix 1
1 6 1 2
1 2 2 16
8 2 14 3
Matrix 2
1 1 1 7
1 1 7 12
8 8 9 2

Key1

给一矩阵每一行每一列的和，求一个可行矩阵。行数列数在[1, 20]之间，每个元素大小在[1,20]之间。

从输入可以得到没一行、每一列的和。以行、列建立二分图。以所有行、所有列为结点，建立源汇点s、t。s向所有行结点建边，上界为该行的和。所有列结点向t建边，上界为该列的和。所有行向所有列建边，上界为20。 由于矩阵每个元素都大于零，可以知道，每条行-列的边下界为1。

使用有源汇有上下界的最大流的方法。s->每个行结点 的c减去m，每个行节点->每个列结点的c减去1（则都变成了19），每个列结点->t的c减去n。然后就是按照通用方法连接t->s，建立超级源汇点ss、st并建立附加边，运行maxflow(ss, st)，然后去除附加边与ss、st，再次运行maxflow(s, t)。行节点->列结点的flow+1即为矩阵元素值。

Code1

#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;

#define INF 0x7FFFFFFF
const int maxn = 50;

struct Edge {
	int c, f;
	unsigned v, flip;
	Edge(unsigned v, int c, int f, unsigned flip) :v(v), c(c), f(f), flip(flip) {}
};

class Dinic {
public:
	bool b[maxn];
	int a[maxn];
	unsigned p[maxn], cur[maxn], d[maxn];
	vector<Edge> G[maxn];

	unsigned s, t;
	void Init(unsigned n) {
		for (int i = 0; i <= n; ++i)
			G[i].clear();
	}

	void AddEdge(unsigned u, unsigned v, int c) {
		G[u].push_back(Edge(v, c, 0, G[v].size()));
		G[v].push_back(Edge(u, 0, 0, G[u].size() - 1));	//使用无向图时将0改为c即可 
	}

	bool BFS() {
		unsigned u, v;
		queue<unsigned> q;
		memset(b, 0, sizeof(b));
		q.push(s);
		d[s] = 0;
		b[s] = 1;
		while (!q.empty()) {
			u = q.front();
			q.pop();
			for (auto it = G[u].begin(); it != G[u].end(); ++it) {
				Edge &e = *it;
				if (!b[e.v] && e.c>e.f) {
					b[e.v] = 1;
					d[e.v] = d[u] + 1;
					q.push(e.v);
				}
			}
		}
		return b[t];
	}

	int DFS(unsigned u, int a) {
		if (u == t || a == 0)
			return a;
		int flow = 0, f;
		for (unsigned &i = cur[u]; i<G[u].size(); ++i) {
			Edge &e = G[u][i];
			if (d[u] + 1 == d[e.v] && (f = DFS(e.v, min(a, e.c - e.f)))>0) {
				a -= f;
				e.f += f;
				G[e.v][e.flip].f -= f;
				flow += f;
				if (!a) break;
			}
		}
		return flow;
	}

	int MaxFlow(unsigned s, unsigned t) {
		int flow = 0;
		this->s = s;
		this->t = t;
		while (BFS()) {
			memset(cur, 0, sizeof(cur));
			flow += DFS(s, INF);
		}
		return flow;
	}
};

int Dif[maxn];
int T, R, C;

int main() {
	scanf("%d", &T);
	for (int Case = 1; Case <= T; ++Case) {
		scanf("%d%d", &R, &C);
		memset(Dif, 0, sizeof(Dif));
		Dinic din;
		const int s = R + C + 1, t = R + C + 2;
		const int ss = s+2, st = t + 2;
		int ipt, last_ipt;
		last_ipt = 0;
		for (int i = 1; i <= R; ++i) {
			scanf("%d", &ipt);
			din.AddEdge(s, i, ipt - last_ipt - C);
			last_ipt = ipt;
			Dif[s] -= C;
			Dif[i] += C;
		}
		last_ipt = 0;
		for (int i = 1; i <= C; ++i) {
			scanf("%d", &ipt);
			din.AddEdge(R + i, t, ipt - last_ipt - R);
			last_ipt = ipt;
			Dif[R + i] -= R;
			Dif[t] += R;
		}
		for (int i = 1; i <= R; ++i) for (int j = 1; j <= C; ++j) {
			din.AddEdge(i, R + j, 20 - 1);
			Dif[i] -= 1;
			Dif[R + j] += 1;
		}
		din.AddEdge(t, s, INF);
		for (int i = 1; i <= R*C+2; ++i) {
			if (Dif[i] > 0) din.AddEdge(ss, i, Dif[i]);
			if (Dif[i] < 0) din.AddEdge(i, st, -Dif[i]);
		}
		din.MaxFlow(ss, st);
		for (auto &e : din.G[ss]) din.G[e.v][e.flip].f = din.G[e.v][e.flip].c = e.c = e.f = 0;
		for (auto &e : din.G[st]) din.G[e.v][e.flip].f = din.G[e.v][e.flip].c = e.c = e.f = 0;
		din.MaxFlow(s, t);
		printf("Matrix %d\n", Case);
		for (int i = 1; i <= R; ++i) {
			for (const auto &e : din.G[i]) if (e.c) {
				printf("%d ", e.f + 1);
			}
			puts("");
		}
	}
	return 0;
}

Key2

上述有源汇有上下界最大流的通用解法之所以通用，是因为“上界减去下界后图中的流量不一定平衡”。而本题的每条边的流量下界被减去后，流量依然是平衡的，所以可以优化。（即上述代码运行完后会发现，Dif[i]均为0，即ss和st没有边连接原图。）

在把s->行的c减去m、行->列的c减去1、列->t的c减去n后，直接运行maxflow(s, t)，行->列的flow加上1即为答案。

Code2

//main函数之前内容一样
int T, R, C;
int main() {
	scanf("%d", &T);
	for (int Case = 1; Case <= T; ++Case) {
		scanf("%d%d", &R, &C);
		Dinic din;
		const int s = R + C + 1, t = R + C + 2;
		int ipt, last_ipt;
		last_ipt = 0;
		for (int i = 1; i <= R; ++i) {
			scanf("%d", &ipt);
			din.AddEdge(s, i, ipt - last_ipt-C);
			last_ipt = ipt;
		}
		last_ipt = 0;
		for (int i = 1; i <= C; ++i) {
			scanf("%d", &ipt);
			din.AddEdge(R + i, t, ipt - last_ipt-R);
			last_ipt = ipt;
		}
		for (int i = 1; i <= R; ++i) for (int j = 1; j <= C;++j) {
			din.AddEdge(i, R + j, 20-1);
		}
		din.MaxFlow(s, t);
		printf("Matrix %d\n", Case);
		for (int i = 1; i <= R; ++i) {
			for (const auto &e : din.G[i]) if (e.c) {
				printf("%d ", e.f+1);
			}
			puts("");
		}
	}
	return 0;
}