题目链接：
题意：输入的第一行是测试数据的个数。每组测试数据的第一行是N和M。第二行是N个数，表示N行的和，第三行是M个数，表示M列的和。接下来一个K，表示有以下K个限制，每个限制的形式X Y Z W，其中Z是< > 或者=，表示第X行第Y列的元素和W的大小关系。假如Z是>，那么说明第X行第Y列的元素必须大于W。如果X是0，意思指所有第Y列的数和W的大小关系；如果Y是0，意思指所有第X行的数和W的大小关系；如果X和Y均为0，则表示整个矩阵和W的大小关系。如果有满足所有条件的矩阵，输出；没有的话，输出IMPOSSIBLE。
思路：上下限最大流。
#include#include #include #define MAX 230#define min(x,y) ((x)<(y)?(x):(y))#define max(x,y) ((x)>(y)?(x):(y))using namespace std;const int INF=1000000000;int high[MAX][MAX],low[MAX][MAX];int cap[MAX][MAX];int in[MAX],out[MAX],inc[MAX],pre[MAX],visit[MAX];int n,m,s,t,ss,tt,sum;int r[MAX],c[MAX];void InPut(){ int i,j,num,u,v,w; char ch; memset(high,0,sizeof(high)); memset(low,0,sizeof(low)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&r[i]); for(i=1;i<=m;i++) scanf("%d",&c[i]); for(i=1;i<=n;i++)for(j=1;j<=m;j++) high[i][j+n]=INF; for(scanf("%d",&num);num--;) { scanf("%d%d %c%d",&u,&v,&ch,&w); if(u==0&&v!=0) { if(ch=='=')for(i=1;i<=n;i++)low[i][v+n]=high[i][v+n]=w; else if(ch=='<')for(i=1;i<=n;i++)high[i][v+n]=min(high[i][v+n],w-1); else for(i=1;i<=n;i++)low[i][v+n]=max(low[i][v+n],w+1); } else if(u!=0&&v==0) { if(ch=='=')for(i=1;i<=m;i++)low[u][i+n]=high[u][i+n]=w; else if(ch=='<')for(i=1;i<=m;i++)high[u][i+n]=min(high[u][i+n],w-1); else for(i=1;i<=m;i++)low[u][i+n]=max(low[u][i+n],w+1); } else if(u==0&&v==0) { for(i=1;i<=n;i++)for(j=1;j<=m;j++) { if(ch=='=') low[i][j+n]=high[i][j+n]=w; else if(ch=='<')high[i][j+n]=min(high[i][j+n],w-1); else low[i][j+n]=max(low[i][j+n],w+1); } } else { if(ch=='=')low[u][v+n]=high[u][v+n]=w; else if(ch=='<')high[u][v+n]=min(high[u][v+n],w-1); else low[u][v+n]=max(low[u][v+n],w+1); } } s=0;t=n+m+1; for(i=1;i<=n;i++)low[s][i]=high[s][i]=r[i]; for(i=1;i<=m;i++)low[i+n][t]=high[i+n][t]=c[i];}int BFS(int s,int t){ int i,u; queue Q; memset(pre,-1,sizeof(pre)); memset(visit,0,sizeof(visit)); Q.push(s);visit[s]=1;inc[s]=INF; while(!Q.empty()) { u=Q.front(); Q.pop(); for(i=0;i<=t;i++) if(!visit[i]&&cap[u][i]) { inc[i]=min(inc[u],cap[u][i]); pre[i]=u; visit[i]=1; if(i==t) return 1; Q.push(i); } } return 0;}int Maxflow(int s,int t){ int maxflow=0,i; memset(inc,0,sizeof(inc)); while(BFS(s,t)) { maxflow+=inc[t]; for(i=t;i!=s;i=pre[i]) { cap[pre[i]][i]-=inc[t]; cap[i][pre[i]]+=inc[t]; } } return maxflow;}int limitMaxflow(){ int i,j,ans; memset(in,0,sizeof(in)); memset(out,0,sizeof(out)); memset(cap,0,sizeof(cap)); for(sum=0,i=0;i<=t;i++) for(j=0;j<=t;j++) { cap[i][j]=high[i][j]-low[i][j]; out[i]+=low[i][j]; in[j]+=low[i][j]; sum+=low[i][j]; } for(ss=t+1,tt=t+2,i=0;i<=t;i++) cap[ss][i]=in[i],cap[i][tt]=out[i]; cap[t][s]=INF; ans=Maxflow(ss,tt); if(ans!=sum) return 0; cap[t][s]=cap[s][t]=0; ans=Maxflow(s,t); return 1;}int C;int main(){ for(scanf("%d",&C);C--;) { InPut(); if(!limitMaxflow()) { puts("IMPOSSIBLE"); continue; } int i,j; for(i=1;i<=n;i++) { for(j=1;j<=m;j++) printf("%d ",cap[j+n][i]+low[i][j+n]); printf("\n"); } } return 0;}