题意：给出一个n*m的矩阵的每行和及每列和，还有一些格子的限制，求一组合法方案。
源点向行，汇点向列，连一条上下界均为和的边。
对于某格的限制，从它所在行向所在列连其上下界的边。
求有源汇上下界可行流即可。
具体做法可以从汇点向源点连容量为正无穷的边，转成无源汇上下界可行流。
然后可以新建超级源汇，对于一条下界为l，上界为r的边(x,y)，从超级源点向y，x向超级汇点连容量为l的边，x向y连容量为r-l的边。
如果那些容量为l的边没满流，则无解。
#include#include #include #include using namespace std;const int inf = 0x3f3f3f3f, N = 230, M = 25000;char op[2];int q,n,m,c,x,y,z,s,t,S,T,e=1,fr,l[205][25],r[205][25],ans[205][25],hd[N],nxt[M],to[M],f[M],ch[N];void add(int x, int y, int z) { to[++e] = y, f[e] = z, nxt[e] = hd[x], hd[x] = e; to[++e] = x, f[e] = 0, nxt[e] = hd[y], hd[y] = e;}void upd(int x, int y) { if(op[0] == '<') r[x][y] = min(r[x][y], z-1); else if(op[0] == '>') l[x][y] = max(l[x][y], z+1); else l[x][y] = max(l[x][y], z), r[x][y] = min(r[x][y], z);}bool tel() { memset(ch, -1, sizeof ch); queue q; q.push(S), ch[S] = 0; while(!q.empty()) { int u = q.front(); q.pop(); for(int i = hd[u]; i; i = nxt[i]) if(ch[to[i]] == -1 && f[i]) ch[to[i]] = ch[u]+1, q.push(to[i]); } return ch[T] != -1;}int zng(int a, int b) { if(a == T) return b; int r = 0; for(int i = hd[a]; i && b > r; i = nxt[i]) if(ch[to[i]] == ch[a]+1 && f[i]) { int rr = zng(to[i], min(b-r, f[i])); f[i] -= rr, f[i^1] += rr, r += rr; } if(!r) ch[a] = -1; return r;}int main() { scanf("%d", &q); while(q--) { e = 1; memset(hd, 0, sizeof hd); memset(l, 0, sizeof l); memset(r, 0x3f, sizeof r); scanf("%d%d", &n, &m), t = n+m+1, S = n+m+2, T = n+m+3, add(t,s,inf); for(int i = 1; i <= n; i++) scanf("%d", &x), add(S,i,x), add(s,T,x); for(int i = 1; i <= m; i++) scanf("%d", &x), add(S,t,x), add(i+n,T,x); scanf("%d", &c); while(c--) { scanf("%d%d%s%d", &x, &y, op, &z); if(!x && !y) { for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) upd(i,j); } else if(!x) { for(int i = 1; i <= n; i++) upd(i,y); } else if(!y) { for(int i = 1; i <= m; i++) upd(x,i); } else upd(x,y); } if(fr) puts(""); fr = 1; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { if(r[i][j] < l[i][j]) {puts("IMPOSSIBLE"); goto aa;} add(i,j+n,r[i][j]-l[i][j]),add(S,j+n,l[i][j]),add(i,T,l[i][j]); } while(tel()) while(zng(S,inf)); for(int i = hd[S]; i; i = nxt[i]) if(f[i]) {puts("IMPOSSIBLE"); goto aa;} for(int i = 1; i <= n; i++) for(int j = hd[i]; j; j = nxt[j]) if(to[j] > n && to[j] <= n+m) ans[i][to[j]-n] = f[j^1]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) printf("%d%c", ans[i][j]+l[i][j], " \n"[j==m]); aa: ; } return 0;}