【题意】
有一个n*m的非负整数矩阵(n<=20,m<=200)，给定每行之和和每列之和，并对一些格子进行约束
例如：
1 2 > 2代表（1,2）格子里的数大于2
0 1 = 2表示第1列的所有数字都等于2
求一种可能的矩阵
【输入】
多组数据
第一行一个数字表示数据组数
每组数据第一行为n、m
接下来n个数表示各行之和
接下来m个数表示各列之和
然后一个数k表示约束的个数
之后k行每行为一个约束
【输出】
对于每组数据，输出一个n*m的矩阵表示一种可能的矩阵
两组输出之间有一个空行分隔
带上下界的网络流问题
0为源，n+m+1为汇，1..n表示矩阵的行，n+1..n+m表示矩阵的列
从0向每个行连一条[该行和,该行和]的边，从n+1..n+m向n+m+1连一条[该列和,该列和]的边
从1..n向n+1..n+m+1各连一条表示该数上下界的边
然后将图转化后即可做最大流即可，1..n到n+1..n+m的每条边的逆流即为其大于下界的值
图转化的方法如下
若存在一条上下界为[a,b]连接(i,j)的边，则从虚拟源点向j连一条流量为a的边，从i向虚拟汇点连一条流量为a的边，再从i向j连一条流量为b-a的边
最后将原汇点向原源点连一条流量为正无穷的边即可
program poj2396;
const
s=222;
e=223;
var
ans,maxn,t,n,m,i,j,k,u,v,f,tot,sum,p,all:longint;
temp:char;
l,r,flow:array [0..301,0..301] of longint;
dl,last,root:array [0..301] of longint;
yes:array [0..301] of boolean;
point,next:array [0..90001] of longint;
procedure connect (s,e,f:longint);
begin
inc(tot);
point[tot]:=e;
next[tot]:=root[s];
root[s]:=tot;
flow[s,e]:=flow[s,e]+f;
end;
function opt (a,b,p:longint):longint;
begin
if a*p>b*p then exit(a)
else exit(b);
end;
procedure quick (s,e:longint;order:char;f:longint);
begin
if order<>'>' then r[s,e]:=opt(r[s,e],f-ord(order='<'),-1);
if order<>'<' then l[s,e]:=opt(l[s,e],f+ord(order='>'),1);
end;
function maxflow (s,e:longint):longint;
begin
ans:=0;
repeat
fillchar(yes,sizeof(yes),false);
yes[s]:=true;
i:=1;
tot:=1;
dl[1]:=s;
while i<=tot do
begin
if dl[i]=e then break;
k:=root[dl[i]];
while k<>0 do
begin
if (not yes[point[k]])and(flow[dl[i],point[k]]>0) then
begin
yes[point[k]]:=true;
inc(tot);
dl[tot]:=point[k];
last[point[k]]:=dl[i];
end;
k:=next[k];
end;
inc(i);
end;
if not yes[e] then break;
maxn:=maxlongint;
i:=e;
while i<>s do
begin
if flow[last[i],i]<maxn then maxn:=flow[last[i],i];
i:=last[i];
end;
ans:=ans+maxn;
i:=e;
while i<>s do
begin
flow[last[i],i]:=flow[last[i],i]-maxn;
flow[i,last[i]]:=flow[i,last[i]]+maxn;
i:=last[i];
end;
until false;
exit(ans);
end;
begin
read(t);
while t<>0 do
begin
fillchar(root,sizeof(root),0);
fillchar(flow,sizeof(flow),0);
read(n,m);
tot:=0;
sum:=0;
all:=0;
for i:=1 to n do
begin
read(f);
all:=all+f;
sum:=sum+f;
connect(s,i,f);
connect(0,e,f);
end;
for i:=1 to m do
begin
read(f);
sum:=sum-f;
all:=all+f;
connect(n+i,e,f);
connect(s,n+m+1,f);
end;
for i:=1 to n do
for j:=1 to m do
begin
l[i,n+j]:=0;
r[i,n+j]:=maxlongint div 10;
end;
read(k);
for p:=1 to k do
begin
read(u,v);
read(temp);
read(temp);
read(f);
if (u=0)and(v=0) then
for i:=1 to n do
for j:=1 to m do
quick(i,n+j,temp,f)
else
if u=0 then
for i:=1 to n do
quick(i,n+v,temp,f)
else
if v=0 then
for i:=1 to m do
quick(u,n+i,temp,f)
else
quick(u,n+v,temp,f);
end;
for i:=1 to n do
for j:=1 to m do
begin
if l[i,n+j]>r[i,n+j] then
begin
sum:=-1;
break;
end;
all:=all+l[i,n+j];
flow[s,n+j]:=flow[s,n+j]+l[i,n+j];
flow[i,e]:=flow[i,e]+l[i,n+j];
flow[i,n+j]:=r[i,n+j]-l[i,n+j];
end;
for i:=1 to n+m do
begin
if flow[s,i]>0 then connect(s,i,0);
if flow[i,e]>0 then connect(i,e,0);
end;
for i:=1 to n do
for j:=1 to m do
if flow[i,n+j]>0 then
begin
connect(i,n+j,0);
connect(n+j,i,0);
end;
connect(n+m+1,0,maxlongint div 10);
if sum<>0 then
writeln('IMPOSSIBLE')
else
begin
k:=maxflow(s,e);
if k<all then
writeln('IMPOSSIBLE')
else
begin
for i:=1 to n do
begin
for j:=1 to m do
write(l[i,n+j]+flow[n+j,i],' ');
writeln;
end;
end;
end;
writeln;
dec(t);
end;
end.