首页 > 代码库 > POJ2396 Budget 【带下界的最大流】
POJ2396 Budget 【带下界的最大流】
Budget
| Time Limit: 3000MS | Memory Limit: 65536K | |||
| Total Submissions: 5962 | Accepted: 2266 | Special Judge | ||
Description
We are supposed to make a budget proposal for this multi-site competition. The budget proposal is a matrix where the rows represent different kinds of expenses and the columns represent different sites. We had a meeting about this, some time ago where we discussed the sums over different kinds of expenses and sums over different sites. There was also some talk about special constraints: someone mentioned that Computer Center would need at least 2000K Rials for food and someone from Sharif Authorities argued they wouldn‘t use more than 30000K Rials for T-shirts. Anyway, we are sure there was more; we will go and try to find some notes from that meeting.
And, by the way, no one really reads budget proposals anyway, so we‘ll just have to make sure that it sums up properly and meets all constraints.
And, by the way, no one really reads budget proposals anyway, so we‘ll just have to make sure that it sums up properly and meets all constraints.
Input
The first line of the input contains an integer N, giving the number of test cases. The next line is empty, then, test cases follow: The first line of each test case contains two integers, m and n, giving the number of rows and columns (m <= 200, n <= 20). The second line contains m integers, giving the row sums of the matrix. The third line contains n integers, giving the column sums of the matrix. The fourth line contains an integer c (c < 1000) giving the number of constraints. The next c lines contain the constraints. There is an empty line after each test case.
Each constraint consists of two integers r and q, specifying some entry (or entries) in the matrix (the upper left corner is 1 1 and 0 is interpreted as "ALL", i.e. 4 0 means all entries on the fourth row and 0 0 means the entire matrix), one element from the set {<, =, >} and one integer v, with the obvious interpretation. For instance, the constraint 1 2 > 5 means that the cell in the 1st row and 2nd column must have an entry strictly greater than 5, and the constraint 4 0 = 3 means that all elements in the fourth row should be equal to 3.
Each constraint consists of two integers r and q, specifying some entry (or entries) in the matrix (the upper left corner is 1 1 and 0 is interpreted as "ALL", i.e. 4 0 means all entries on the fourth row and 0 0 means the entire matrix), one element from the set {<, =, >} and one integer v, with the obvious interpretation. For instance, the constraint 1 2 > 5 means that the cell in the 1st row and 2nd column must have an entry strictly greater than 5, and the constraint 4 0 = 3 means that all elements in the fourth row should be equal to 3.
Output
For each case output a matrix of non-negative integers meeting the above constraints or the string "IMPOSSIBLE" if no legal solution exists. Put one empty line between matrices.
Sample Input
2 2 3 8 10 5 6 7 4 0 2 > 2 2 1 = 3 2 3 > 2 2 3 < 5 2 2 4 5 6 7 1 1 1 > 10
Sample Output
2 3 3 3 3 4 IMPOSSIBLE
Source
Tehran 2003 Preliminary
这题做得真是抓狂啊，前前后后断断续续用了三天时间，主要时间都卡在一个手误上，敲错了一个字母...
题意：有一个n*m 的方阵, 方阵里面的数字未知, 但是我们知道如下约束条件:
1> 每一行的数字的和
2> 每一列的数字的和
3> 某些格子里的数，大小有限制。比如规定第2行第3 列的数字必须大于5( 或必须小于3, 或必须等于10等）
求解是否存在在满足所有的约束的条件下用正数来填充该方阵的方案, 若有, 输出填充后的方阵, 否则输出IMPOSSIBLE.
题解：这道题可以转化成容量有上下界的最大流问题, 将方阵的行从1……n 编号, 列n+1……n+m 编号, 添加源点s=0 和汇点t=n+m+1.
1> 将源点和每一个行节点相连, 相连所形成的边的容量和下界置为该行所有数字的和
2> 将每一个列节点和汇点相连, 相连所形成的边的容量和下界都置为该列所有数字的和
3> 从每个行节点到每个列节点连边，容量为无穷大
4> 如果u 行v 列的数字必须大于w, 则边<u,v+n> 流量的下界是w+1
5> 如果u 行v 列的数字必须小于w, 则边<u,v+n> 容量改为w-1
6> 如果u 行v 列的数字必须等于w, 则边<u,v+n> 流量的下界和容量都是w
找到的可行流（也是最大流），就是问题的解
本题trick:
1) W 可能为负数，产生流量下界为负数的情况。应处理成0
2) 数据本身可能矛盾。比如前面说了 (2,1) =1, 后面又说(2,1) = 10
#include <stdio.h>
#include <string.h>
#define inf 0x3fffffff
#define maxn 250
int m, n, sink, ssource, ssink; // m rows, n columns
int G[maxn][maxn], G0[maxn][maxn], flow[maxn][maxn];
int low[maxn][maxn], high[maxn][maxn];
int in[maxn], out[maxn], Layer[maxn], que[maxn];
bool vis[maxn];
int min(int a, int b) {
return a > b ? b : a;
}
int max(int a, int b) {
return a < b ? b : a;
}
bool countLayer() {
memset(Layer, 0, sizeof(Layer));
int i, now, id = 0, front = 0;
Layer[ssource] = 1; que[id++] = ssource;
while(front < id) {
now = que[front++];
for(i = 0; i <= ssink; ++i)
if(G[now][i] > 0 && !Layer[i]) {
Layer[i] = Layer[now] + 1;
if(i == ssink) return true;
else que[id++] = i;
}
}
return false;
}
int Dinic() {
int maxFlow = 0, minCut, pos, i, now, u, v, id = 0;
while(countLayer()) {
memset(vis, 0, sizeof(vis));
vis[ssource] = 1; que[id++] = ssource;
while(id) {
now = que[id - 1];
if(now == ssink) {
minCut = inf;
for(i = 1; i < id; ++i) {
u = que[i - 1];
v = que[i];
if(minCut > G[u][v]) {
minCut = G[u][v];
pos = u;
}
}
maxFlow += minCut;
for(i = 1; i < id; ++i) {
u = que[i - 1];
v = que[i];
G[u][v] -= minCut;
G[v][u] += minCut;
flow[u][v] += minCut;
flow[v][u] -= minCut;
}
while(que[id - 1] != pos)
vis[que[--id]] = 0;
} else {
for(i = 0; i <= ssink; ++i) {
if(G[now][i] > 0 && Layer[now] + 1 == Layer[i] && !vis[i]) {
vis[i] = 1; que[id++] = i; break;
}
}
if(i > ssink) --id;
}
}
}
return maxFlow;
}
void solve() {
int i, j, sum = 0;
for(i = 0; i <= sink; ++i)
for(j = 0; j <= sink; ++j) {
G[i][j] = high[i][j] - low[i][j];
out[i] += low[i][j];
in[j] += low[i][j];
sum += low[i][j];
}
for(i = 0; i <= sink; ++i) {
G[ssource][i] = in[i];
G[i][ssink] = out[i];
}
// memcpy(G0, G, sizeof(G));
G[sink][0] = inf;
if(sum != Dinic()) {
printf("IMPOSSIBLE\n");
return;
}
G[sink][0] = G[0][sink] = 0;
for(i = 1; i <= m; ++i) {
// printf("%d", G0[i][1 + m] - G[i][1 + m] + low[i][1 + m]);
printf("%d", flow[i][1 + m] + low[i][1 + m]);
for(j = 2; j <= n; ++j)
printf(" %d", flow[i][j + m] + low[i][j + m]);
printf("\n");
}
}
int main() {
// freopen("POJ2396.txt", "r", stdin);
// freopen("ans1.txt", "w", stdout);
int t, c, x, y, z, i, j;
char ch;
scanf("%d", &t);
while(t--) {
memset(G, 0, sizeof(G));
memset(low, 0, sizeof(low));
memset(high, 0, sizeof(high));
memset(out, 0, sizeof(out));
memset(in, 0, sizeof(in));
memset(flow, 0, sizeof(flow));
scanf("%d%d", &m, &n);
sink = m + n + 1;
ssource = sink + 1;
ssink = ssource + 1;
for(i = 1; i <= m; ++i) {
scanf("%d", &z);
low[0][i] = high[0][i] = z;
}
for(i = 1; i <= n; ++i) {
scanf("%d", &z);
low[m + i][sink] = high[m + i][sink] = z;
}
for(i = 1; i <= m; ++i) {
for(j = 1; j <= n; ++j) {
high[i][j + m] = inf;
}
}
scanf("%d", &c);
while(c--) {
scanf("%d%d %c %d", &x, &y, &ch, &z);
if(!x && y) { // 所有行的第y个元素
if(ch == '=') {
for(i = 1; i <= m; ++i)
low[i][m + y] = high[i][m + y] = z;
} else if(ch == '<') {
for(i = 1; i <= m; ++i)
high[i][m + y] = min(z - 1, high[i][m + y]);
} else {
for(i = 1; i <= m; ++i)
low[i][m + y] = max(z + 1, low[i][m + y]);
}
} else if(x && !y) {
if(ch == '=') {
for(i = 1; i <= n; ++i)
low[x][m + i] = high[x][m + i] = z;
} else if(ch == '<') {
for(i = 1; i <= n; ++i)
high[x][m + i] = min(high[x][m + i], z - 1);
} else {
for(i = 1; i <= n; ++i)
low[x][m + i] = max(low[x][m + i], z + 1);
}
} else if(!x && !y) {
for(i = 1; i <= m; ++i)
for(j = 1; j <= n; ++j) {
if(ch == '=')
low[i][m + j] = high[i][m + j] = z;
else if(ch == '<')
high[i][m + j] = min(high[i][m + j], z - 1);
else low[i][m + j] = max(low[i][m + j], z + 1);
}
} else {
if(ch == '=')
low[x][m + y] = high[x][m + y] = z;
else if(ch == '<')
high[x][m + y] = min(high[x][m + y], z - 1);
else low[x][m + y] = max(low[x][m + y], z + 1);
}
}
solve();
printf("\n");
}
return 0;
}POJ2396 Budget 【带下界的最大流】
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。