POJ2396

一直调了3天还是RE，求调！

#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int MAXM = 10005;
const int MAXN = 1005;
const int INF = 0x3f3f3f3f;
struct Node {
    int next, to, cap, flow;
} e[MAXM * 2];
int h[MAXN], tot, deg[MAXN], dep[MAXN];
int n, m;
int low[MAXN][MAXN], up[MAXN][MAXN];
void add(int u, int v, int cap) {
    e[tot] = {h[u], v, cap, 0};
    h[u] = tot++;
}
void add_edge(int u, int v, int cap) {
    add(u, v, cap);
    add(v, u, 0);
}
void add_edge(int u, int v, int l, int r) {
    add_edge(u, v, r - l);
    deg[u] -= l;
    deg[v] += l;
}
void init() {
    memset(h, 0xff, sizeof h);
    memset(deg, 0, sizeof deg);
    memset(dep, 0, sizeof dep);
    memset(low, 0, sizeof low);
    memset(up, 0x3f, sizeof up);
    tot = 0;
}
bool bfs(int s, int t) {
    memset(dep, 0, sizeof dep);
    dep[s] = 1;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int i = h[u]; ~i; i = e[i].next) {
            int v = e[i].to;
            if (!dep[v] and e[i].cap > e[i].flow) {
                dep[v] = dep[u] + 1;
                q.push(v);
                if (v == t) return true;
            }
        }
    }
    return false;
}
int dfs(int u, int f, int t) {
    if (u == t) return f;
    int r = f;
    for (int i = h[u]; ~i and r > 0; i = e[i].next) {
        int v = e[i].to;
        if (dep[v] == dep[u] + 1 and e[i].cap > e[i].flow) {
            int k = dfs(v, min(r, e[i].cap - e[i].flow), t);
            if (k == 0) dep[v] = 0;
            e[i].flow += k;
            e[i^1].flow -= k;
            r -= k;
        }
    }
    return f - r;
}
int dinic(int s, int t) {
    int tmp = 0;
    while (bfs(s, t)) tmp += dfs(s, INF, t);
    return tmp;
}
bool flag;
void solve() {
    init();
    scanf("%d%d", &n, &m);
    int S = n + m + 1, T = n + m + 2, SS = n + m + 3, TT = n + m + 4;
    for (int i = 1; i <= n; i++) {
        int t;
        scanf("%d", &t);
        add_edge(S, i, t, t);
    }
    for (int i = 1; i <= m; i++) {
        int t;
        scanf("%d", &t);
        add_edge(i + n, T, t, t);
    }
    int k;
    scanf("%d", &k);
    for (int i = 1; i <= k; i++) {
        int a, b, val, x1, x2, y1, y2;
        char opt;
        scanf("%d %d %c %d", &a, &b, &opt, &val);
        if (a == 0) {
            x1 = 1;
            x2 = n;
        } else {
            x1 = x2 = a;
        }
        if (b == 0) {
            y1 = 1;
            y2 = m;
        } else {
            y1 = y2 = b;
        }
        for (int x = x1; x <= x2; x++) {
            for (int y = y1; y <= y2; y++) {
                if (opt == '>') {
                    low[x][y] = max(low[x][y], val + 1);
                } else if (opt == '<') {
                    up[x][y] = min(up[x][y], val - 1);
                } else {
                    low[x][y] = max(low[x][y], val);
                    up[x][y] = min(up[x][y], val);
                }
                if (low[x][y] > up[x][y]) {
                    printf("IMPOSSIBLE\n");
                    return;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            add_edge(i, j + n, low[i][j], up[i][j]);
        }
    }
    int num = 0;
    for (int i = 1; i <= T; i++) {
        if (deg[i] > 0) {
            add_edge(SS, i, deg[i]);
            num += deg[i];
        }
        if (deg[i] < 0) {
            add_edge(i, TT, -deg[i]);
        }
    }
    add_edge(T, S, INF);
    int ans = dinic(SS, TT);
    if (ans != num) {
        printf("IMPOSSIBLE\n");
    } else {
        for (int u = 1; u <= n; u++) {
            for (int i = h[u]; ~i; i = e[i].next) {
                if (i & 1 == 1) continue;
                int v = e[i].to;
                v -= n;
                if (1 <= v and v <= m)
                    low[u][v] += e[i].flow;
            }
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                printf("%d", low[i][j]);
                if (j == m) printf("\n");
                else printf(" ");
            }
        }
        printf("\n");
    }
}
int main() {
    // freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
    int t;
    scanf("%d", &t);
    while (t--) solve();
    fflush(stdout);
    return 0;
}

使用有源汇上下界网络流，类似二分图的建图，把一行看成一个点，一列看成一个点。