POJ 2175 Evacuation Plan——消负圈算法求费用流

这道题普通的连续最短路算法会超时，我们发现题目不需要求最小的费用流，只需要求一个较小的费用流就可以，所以通过消负圈算法高效求解

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
const int maxn = 500;
const int INF = 0x3f3f3f3f;
int n, m;
int X[maxn], Y[maxn], B[maxn], P[maxn], Q[maxn], C[maxn], E[maxn][maxn];
int g[maxn][maxn];
int prevv[maxn][maxn];
bool used[maxn];
void solve() {
    int V = n + m + 1;
    memset(g, INF, sizeof(g));
    for (int j = 0; j < m; j++) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int c = abs(X[i]-P[j])+abs(Y[i]-Q[j])+1;
            g[i][n+j] = c;
            if (E[i][j] > 0) g[n+j][i] = -c;
            sum += E[i][j];
        }
        if (sum > 0) g[n+m][n+j] = 0;
        if (sum < C[j]) g[n+j][n+m] = 0;
    }
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            prevv[i][j] = i;
        }
    }
    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (g[i][j] > g[i][k] + g[k][j]) {
                    g[i][j] = g[i][k] + g[k][j];
                    prevv[i][j] = prevv[k][j];
                    if (i == j && g[i][j] < 0) {
                        memset(used, false, sizeof(used));
                        for (int v = i; !used[v]; v = prevv[i][v]) {
                            used[v] = true;
                            if (v != n+m && prevv[i][v] != n+m) {
                                if (v >= n) E[prevv[i][v]][v-n]++;
                                else E[v][prevv[i][v]-n]--;
                            }
                        }
                        printf("SUBOPTIMAL\n");
                        for (int x = 0; x < n; x++) {
                            for (int y = 0; y < m; y++) {
                                printf("%d%c", E[x][y], y+1==m ? '\n' : ' ');
                            }
                        }
                        return;
                    }
                }
            }
        }
    }
    printf("OPTIMAL\n");
}
int main() {
    while (~scanf("%d %d", &n, &m)) {
        for (int i = 0; i < n; i++) scanf("%d %d %d", &X[i], &Y[i], &B[i]);
        for (int i = 0; i < m; i++) scanf("%d %d %d", &P[i], &Q[i], &C[i]);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) scanf("%d", &E[i][j]);
        }
        solve();
    }
    return 0;
}