UVA 11082 Matrix Decompressing——抽象建图+最大流

UVA 11082 Matrix Decompressing——抽象建图+最大流

#include #include #include #include #include #include using namespace std;const int INF = 0x3f3f3f3f;const int maxn = 500;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 edges; vector G[maxn]; int p[maxn], a[maxn]; void init(int x) { n = x; edges.clear(); for (int i = 0; i < n; i++) G[i].clear(); } void addedge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } int maxflow(int s, int t) { int flow = 0; while (true) { memset(a, 0, sizeof(a)); queue q; q.push(s); p[s] = 0, a[s] = INF; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (!a[e.to] && e.cap > e.flow) { p[e.to] = G[u][i]; a[e.to] = min(a[u], e.cap - e.flow); 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]^1].flow -= a[t]; } flow += a[t]; } return flow; } void outputflow(int R, int C) { for (int i = 1; i <= R; i++) { int flag = 0; for (int j = 0; j < C; j++) { if (flag++) printf(" "); //cout << G[i][j]; printf("%d", edges[G[i][j]].flow + 1); } printf("\n"); } }}ek;int main() { int T; scanf("%d", &T); int R, C, x[maxn], y[maxn]; for (int kase = 1; kase <= T; kase++) { scanf("%d %d", &R, &C); ek.init(R + C + 10); for (int i = 1; i <= R; i++) scanf("%d", &x[i]); for (int i = 1; i <= C; i++) scanf("%d", &y[i]); for (int i = R; i > 1; i--) { x[i] -= x[i - 1]; } for (int j = C; j > 1; j--) { y[j] -= y[j - 1]; } int s = 0, t = R + C + 1; for (int i = 1; i <= R; i++) { for (int j = 1; j <= C; j++) { ek.addedge(i, j + R, 19); } } for (int i = 1; i <= R; i++) { ek.addedge(s, i, x[i] - C); } for (int i = 1; i <= C; i++) { ek.addedge(i + R, t, y[i] - R); } ek.maxflow(s, t); if (kase != 1) printf("\n"); printf("Matrix %d\n", kase); ek.outputflow(R, C); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。