POJ_2396
第一次接触有上下界的网络流问题，感觉只要按套路来就可以了，具体的算法可以参考：。
#include#include #include #define MAXN 210#define MAXM 30#define MAXV 230#define MAXE 24900#define INF 0x3f3f3f3fint N, M, low[MAXN][MAXM], high[MAXN][MAXM], R[MAXN], C[MAXM];int S, T, SS, TT, first[MAXV], e, next[MAXE], v[MAXE], flow[MAXE];int d[MAXV], q[MAXV], work[MAXV];int id[MAXN][MAXM];void update(int x1, int x2, int y1, int y2, char op, int z){ int i, j; for(i = x1; i <= x2; i ++) for(j = y1; j <= y2; j ++) { if(op == '=') low[i][j] = std::max(low[i][j], z), high[i][j] = std::min(high[i][j], z); else if(op == '<') high[i][j] = std::min(high[i][j], z - 1); else low[i][j] = std::max(low[i][j], z + 1); }}void init(){ int i, j, k, x, y, z, n; char op[5]; scanf("%d%d", &N, &M); memset(low, 0, sizeof(low)), memset(high, 0x3f, sizeof(high)); for(i = 1; i <= N; i ++) scanf("%d", &R[i]); for(i = 1; i <= M; i ++) scanf("%d", &C[i]); scanf("%d", &n); for(k = 0; k < n; k ++) { scanf("%d%d%s%d", &x, &y, op, &z); if(x == 0 && y == 0) update(1, N, 1, M, op[0], z); else if(x == 0) update(1, N, y, y, op[0], z); else if(y == 0) update(x, x, 1, M, op[0], z); else update(x, x, y, y, op[0], z); }}int check(){ for(int i = 1; i <= N; i ++) for(int j = 1; j <= M; j ++) if(low[i][j] > high[i][j]) return 0; return 1;}void add(int x, int y, int z){ v[e] = y, flow[e] = z; next[e] = first[x], first[x] = e ++; }int build(){ int i, j, sum = 0; S = 0, T = N + M + 1, SS = T + 1, TT = SS + 1; memset(first, -1, sizeof(first[0]) * (TT + 1)), e = 0; add(T, S, INF), add(S, T, 0); for(i = 1; i <= N; i ++) { add(SS, i, R[i]), add(i, SS, 0), add(S, TT, R[i]), add(TT, S, 0); sum += R[i]; } for(i = 1; i <= M; i ++) { add(SS, T, C[i]), add(T, SS, 0), add(N + i, TT, C[i]), add(TT, N + i, 0); sum += C[i]; } for(i = 1; i <= N; i ++) for(j = 1; j <= M; j ++) { add(i, N + j, high[i][j] - low[i][j]), id[i][j] = e, add(N + j, i, 0); add(SS, N + j, low[i][j]), add(N + j, SS, 0), add(i, TT, low[i][j]), add(TT, i, 0); sum += low[i][j]; } return sum; }int bfs(int S, int T){ int i, j, rear = 0; memset(d, -1, sizeof(d[0]) * (T + 1)); d[S] = 0, q[rear ++] = S; for(i = 0; i < rear; i ++) for(j = first[q[i]]; j != -1; j = next[j]) if(flow[j] && d[v[j]] == -1) { d[v[j]] = d[q[i]] + 1, q[rear ++] = v[j]; if(v[j] == T) return 1; } return 0;}int dfs(int cur, int a, int T){ if(cur == T) return a; for(int &i = work[cur]; i != -1; i = next[i]) if(flow[i] && d[v[i]] == d[cur] + 1) if(int t = dfs(v[i], std::min(a, flow[i]), T)) { flow[i] -= t, flow[i ^ 1] += t; return t; } return 0;}int dinic(int S, int T){ int ans = 0, t; while(bfs(S, T)) { memcpy(work, first, sizeof(first[0]) * (T + 1)); while(t = dfs(S, INF, T)) ans += t; } return ans;}void print(){ int i, j; for(i = 1; i <= N; i ++) { printf("%d", flow[id[i][1]] + low[i][1]); for(j = 2; j <= M; j ++) printf(" %d", flow[id[i][j]] + low[i][j]); printf("\n"); }}void solve(){ if(!check()) { printf("IMPOSSIBLE\n"); return ; } int sum = build(); if(sum != dinic(SS, TT)) printf("IMPOSSIBLE\n"); else print();}int main(){ int t; scanf("%d", &t); while(t --) { init(); solve(); if(t) printf("\n"); } return 0;}