首页 > 代码库 > POJ 2396 Budget （有源汇有上下界的可行流）
POJ 2396 Budget （有源汇有上下界的可行流）
POJ 2396 Budget
链接：http://poj.org/problem?id=2396
题意：给定一个M*N的矩阵，给定每行每列的和，以及其中一些值的限定条件，问能否构成一个可行的矩阵。
思路：
添加一个源点，向每行连边，每条边的上下界都为该行的和；添加一个汇点，每列向汇点连边，边的上下界都为该列的和。然后每行向每列连边，边的上下界一开始为（0，INF），之后通过一些限定条件更新。
现在问题成了求一个有源汇有上下界的可行流。只需要再添加一个超级源点，一个超级汇点，并且将原图的汇点向源点连边，求一个可行流即可。
细节：这道题目的构图比较麻烦。
/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define INF (1 << 30)
#define LINF (1LL << 60)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(i, a, n) for (int i = a; i < n; i++)
#define per(i, a, n) for (int i = n - 1; i >= a; i--)
#define eps 1e-6
#define debug puts("===============")
#define pb push_back
#define mkp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define POSIN(x,y) (0 <= (x) && (x) < n && 0 <= (y) && (y) < m)
typedef long long ll;
typedef unsigned long long ULL;
const int maxn = 2000;
const int maxm = 2000000;
struct node {
int v; // vertex
int cap; // capacity
int flow; // current flow in this arc
int nxt;
} e[maxm * 2];
int g[maxn], cnt;
int st, ed, n, N, M, S, T;
int id[maxm];
void add(int u, int v, int c, int k) {
e[++cnt].v = v;
e[cnt].cap = c;
e[cnt].flow = 0;
e[cnt].nxt = g[u];
g[u] = cnt;
id[k] = cnt;
e[++cnt].v = u;
e[cnt].cap = 0;
e[cnt].flow = 0;
e[cnt].nxt = g[v];
g[v] = cnt;
id[0] = 0;
}
int sum1, sum2;
int low[maxm], up[maxm], tot[maxn];
bool flag;
bool set_edge(int i, int j, char* str, int c) {
int x = (i - 1) * N + j;
if (str[0] == '=') {
if (low[x] <= c && c <= up[x]) low[x] = up[x] = c;
else return false;
}
else if (str[0] == '<') {
if (low[x] < c) up[x] = min(up[x], c - 1);
else return false;
}
else if (str[0] == '>') {
if (up[x] > c) low[x] = max(low[x], c + 1);
else return false;
}
return true;
}
int sum;
void init() {
memset(g, 0, sizeof(int) * (M + N + 10));
memset(tot, 0, sizeof(int) * (M + N + 10));
cnt = 1;
st = M + N + 2, ed = M + N + 3;
S = 0, T = M + N + 1;
int u, v, c;
sum1 = sum2 = 0;
for (int i = 1; i <= M; i++) {
scanf("%d", &c);
tot[S] -= c;
tot[i] += c;
sum1 += c;
}
for (int i = 1; i <= N; i++) {
scanf("%d", &c);
tot[T] += c;
tot[i + M] -= c;
sum2 += c;
}
flag = true;
if (sum1 != sum2) flag = false;
int k;
scanf("%d", &k);
memset(low, 0, sizeof(int) * (M * N + 10));
fill(up, up + sizeof(int) * (M * N + 10), INF);
char str[10];
while(k--) {
scanf("%d%d%s%d", &u, &v, str, &c);
if (flag) {
int rst, red, cst, ced;
if (u == 0) rst = 1, red = M;
else rst = red = u;
if (v == 0) cst = 1, ced = N;
else cst = ced = v;
for (int i = rst; i <= red; i++) {
for (int j = cst; j <= ced; j++) {
if (!set_edge(i, j, str, c)) {
flag = false;
goto FK;
}
}
}
FK:;
}
}
if (!flag) return ;
add(T, S, INF, 0);
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= N; j++) {
int x = (i - 1) * N + j;
tot[i] -= low[x];
tot[j + M] += low[x];
add(i, j + M, up[x] - low[x], x);
}
}
sum = 0;
for (int i = 0; i <= M + N + 1; i++) {
if (tot[i] > 0) add(st, i, tot[i], 0), sum += tot[i];
if (tot[i] < 0) add(i, ed, -tot[i], 0);
}
n = ed + 3;
}
int dist[maxn], numbs[maxn], q[maxn];
void rev_bfs() {
int font = 0, rear = 1;
for (int i = 0; i <= n; i++) { //n为总点数
dist[i] = maxn;
numbs[i] = 0;
}
q[font] = ed;
dist[ed] = 0;
numbs[0] = 1;
while(font != rear) {
int u = q[font++];
for (int i = g[u]; i; i = e[i].nxt) {
if (e[i ^ 1].cap == 0 || dist[e[i].v] < maxn) continue;
dist[e[i].v] = dist[u] + 1;
++numbs[dist[e[i].v]];
q[rear++] = e[i].v;
}
}
}
int maxflow() {
rev_bfs();
int u, totalflow = 0;
int curg[maxn], revpath[maxn];
for(int i = 0; i <= n; ++i) curg[i] = g[i];
u = st;
while(dist[st] < n) {
if(u == ed) { // find an augmenting path
int augflow = INF;
for(int i = st; i != ed; i = e[curg[i]].v)
augflow = min(augflow, e[curg[i]].cap);
for(int i = st; i != ed; i = e[curg[i]].v) {
e[curg[i]].cap -= augflow;
e[curg[i] ^ 1].cap += augflow;
e[curg[i]].flow += augflow;
e[curg[i] ^ 1].flow -= augflow;
}
totalflow += augflow;
u = st;
}
int i;
for(i = curg[u]; i; i = e[i].nxt)
if(e[i].cap > 0 && dist[u] == dist[e[i].v] + 1) break;
if(i) { // find an admissible arc, then Advance
curg[u] = i;
revpath[e[i].v] = i ^ 1;
u = e[i].v;
} else { // no admissible arc, then relabel this vertex
if(0 == (--numbs[dist[u]])) break; // GAP cut, Important!
curg[u] = g[u];
int mindist = n;
for(int j = g[u]; j; j = e[j].nxt)
if(e[j].cap > 0) mindist = min(mindist, dist[e[j].v]);
dist[u] = mindist + 1;
++numbs[dist[u]];
if(u != st)
u = e[revpath[u]].v; // Backtrack
}
}
return totalflow;
}
int main () {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &M, &N);
init();
if (!flag) puts("IMPOSSIBLE");
else {
int dd = maxflow();
if (dd != sum) {
puts("IMPOSSIBLE");
continue;
}
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= N; j++) {
int x = (i - 1) * N + j;
printf("%d%c", low[x] + e[id[x]].flow, j == N ? '\n' : ' ');
}
}
}
if (T) puts("");
}
return 0;
}
POJ 2396 Budget （有源汇有上下界的可行流）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。