一个m行n列的矩阵，给出每行每列中元素的和，以及对一些格子的大小限制，求一个可行方案，输出矩阵。
大小限制形如：严格大于i，严格小于i，等于i。
1<=m<=200.1<=n<=20.
有源汇上下界可行流。
将每一行作为一个点，每一列作为一个点。
源点向每个行点连一条上下界均为该行和的边。
每个列点向汇点连一条上下界均为该列和的边。
每个行点向各列点连一条上下界为该行该列对应点的上下限的边。
然后做一遍有源汇上下界可行流就好了。
（汇点向源点连一条上界为正无穷下界为0的边，就转成无源汇上下界可行流啦！
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int dian=;
const int bian=;
const int INF=0x3f3f3f3f;
int h[dian],nxt[bian],ver[bian],val[bian],ch[dian],cr[dian];
int sx[][],xx[][],bh[][],in[dian],out[dian];
int n,m,aa,bb,cc,tot,num,flag,summ;
int S,T,SS,TT;
char la[];
void add(int a,int b,int c,int d){
tot++;ver[tot]=b;val[tot]=d-c;nxt[tot]=h[a];h[a]=tot;
tot++;ver[tot]=a;val[tot]=;nxt[tot]=h[b];h[b]=tot;
in[b]+=c;
out[a]+=c;
}
bool tell(){
memset(ch,-,sizeof(ch));
queue<int>q;
q.push(S);
ch[S]=;
while(!q.empty()){
int t=q.front();
q.pop();
for(int i=h[t];i;i=nxt[i])
if(ch[ver[i]]==-&&val[i]){
ch[ver[i]]=ch[t]+;
q.push(ver[i]);
}
}
return ch[T]!=-;
}
int zeng(int a,int b){
if(a==T)
return b;
int r=;
for(int i=cr[a];i&&b>r;i=nxt[i])
if(ch[ver[i]]==ch[a]+&&val[i]){
int t=zeng(ver[i],min(b-r,val[i]));
val[i]-=t,r+=t,val[i^]+=t;
if(val[i])
cr[a]=i;
}
if(!r)
ch[a]=-;
return r;
}
int dinic(){
int r=,t;
while(tell()){
for(int i=;i<=n+m+;i++)
cr[i]=h[i];
while(t=zeng(S,INF))
r+=t;
}
return r;
}
int main(){
int cas;
scanf("%d",&cas);
while(cas--){
memset(h,,sizeof(h));
memset(nxt,,sizeof(nxt));
memset(sx,0x3f,sizeof(sx));
memset(xx,,sizeof(xx));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
tot=;
summ=;
scanf("%d%d",&n,&m);
SS=n+m+,TT=n+m+,S=n+m+,T=n+m+;
for(int i=;i<=n;i++){
scanf("%d",&aa);
add(SS,i,aa,aa);
}
for(int i=;i<=m;i++){
scanf("%d",&aa);
add(n+i,TT,aa,aa);
}
scanf("%d",&num);
while(num--){
scanf("%d%d%s%d",&aa,&bb,la,&cc);
if(!aa&&!bb){
for(int i=;i<=n;i++)
for(int j=;j<=m;j++){
if(la[]=='<')
sx[i][j]=min(sx[i][j],cc-);
else if(la[]=='>')
xx[i][j]=max(xx[i][j],cc+);
else{
sx[i][j]=min(sx[i][j],cc);
xx[i][j]=max(xx[i][j],cc);
}
}
}
else if(!aa){
for(int i=;i<=n;i++){
if(la[]=='<')
sx[i][bb]=min(sx[i][bb],cc-);
else if(la[]=='>')
xx[i][bb]=max(xx[i][bb],cc+);
else{
sx[i][bb]=min(sx[i][bb],cc);
xx[i][bb]=max(xx[i][bb],cc);
}
}
}
else if(!bb){
for(int i=;i<=m;i++){
if(la[]=='<')
sx[aa][i]=min(sx[aa][i],cc-);
else if(la[]=='>')
xx[aa][i]=max(xx[aa][i],cc+);
else{
sx[aa][i]=min(sx[aa][i],cc);
xx[aa][i]=max(xx[aa][i],cc);
}
}
for(int i=;i<=n;i++){
if(la[]=='<')
sx[i][bb]=min(sx[i][bb],cc-);
else if(la[]=='>')
xx[i][bb]=max(xx[i][bb],cc+);
else{
sx[i][bb]=min(sx[i][bb],cc);
xx[i][bb]=max(xx[i][bb],cc);
}
}
}
else{
if(la[]=='<')
sx[aa][bb]=min(sx[aa][bb],cc-);
else if(la[]=='>')
xx[aa][bb]=max(xx[aa][bb],cc+);
else{
sx[aa][bb]=min(sx[aa][bb],cc);
xx[aa][bb]=max(xx[aa][bb],cc);
}
}
}
flag=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(sx[i][j]>=xx[i][j]){
bh[i][j]=tot+;
add(i,n+j,xx[i][j],sx[i][j]);
}
else{
flag=;
break;
}
}
if(flag)
break;
}
if(flag){
puts("IMPOSSIBLE");
puts("");
continue;
}
add(TT,SS,,INF);
for(int i=;i<=TT;i++){
if(in[i]-out[i]>)
add(S,i,,in[i]-out[i]);
else if(out[i]-in[i]>){
add(i,T,,out[i]-in[i]);
summ=summ+out[i]-in[i];
}
}
if(dinic()!=summ){
puts("IMPOSSIBLE");
puts("");
continue;
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++)
printf("%d ",xx[i][j]+val[bh[i][j]^]);
puts("");
}
puts("");
}
return ;
}
注意：
一个格子可能有多重限制，上限取min下限取max。
上限可能小于下限要判掉。
每组数据输出间有空行（不加也没事？）。
如果wa了就再读一遍建图，不行就再读一遍。