[UVa] 563 Crimewave.cpp

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

#define INF 9999999
#define MAX 2*52*52+10
vector<int> edge[MAX];
int cap[MAX][MAX], flow[MAX][MAX];
int bottleneck[MAX], pre[MAX];

void BuildGraph(int S, int T, int H, int W);
int MaxFlow(int S, int T, int H, int W);

int main()
{
    int Case, H, W, B, x, y;
    scanf("%d", &Case);
    while (Case--) {
        scanf("%d %d %d", &H, &W, &B);

        int S = 0,      // super source
            T = 1;      // super sink

        for (int i = 0; i <= 2*(H+1)*W; ++i) edge[i].clear();
        memset(cap, 0, sizeof(cap));
        memset(flow, 0, sizeof(flow));

        BuildGraph(S, T, H, W);

        for (int i = 0; i < B; ++i) {
            scanf("%d %d", &x, &y);
            cap[S][(x*H+y)*2] = 1;
            edge[S].push_back((x*H+y)*2);
        }

        if (MaxFlow(S, T, H, W) == B) puts("possible");
        else puts("not possible");
    }
}
void BuildGraph(int S, int T, int H, int W)
{
    for (int i = 1; i <= H; ++i) {
        for (int j = 1; j <= W; ++j) {
            cap[(i*H+j)*2][(i*H+j)*2+1] = 1;     // u  to u'
            edge[(i*H+j)*2].push_back((i*H+j)*2+1);

            cap[(i*H+j)*2+1][((i-1)*H+j)*2] = 1; // u' to up
            edge[(i*H+j)*2+1].push_back(((i-1)*H+j)*2);

            cap[(i*H+j)*2+1][((i+1)*H+j)*2] = 1; // u' to down
            edge[(i*H+j)*2+1].push_back(((i+1)*H+j)*2);

            cap[(i*H+j)*2+1][(i*H+j-1)*2] = 1;   // u' to left
            edge[(i*H+j)*2+1].push_back((i*H+j-1)*2);

            cap[(i*H+j)*2+1][(i*H+j+1)*2] = 1;   // u' to right
            edge[(i*H+j)*2+1].push_back((i*H+j+1)*2);

            if (i == 1 || j == 1 || i == H || j == W) {// if on the edge
                cap[(i*H+j)*2+1][T] = 1;               // connect u' to the T
                edge[(i*H+j)*2+1].push_back(T);
            }
        }
    }
}
int MaxFlow(int S, int T, int H, int W)
{
    int result = 0;
    while (1) {
        memset(bottleneck, 0, sizeof(bottleneck));
        bottleneck[S] = INF;
        queue<int> Q;
        Q.push(S);

        // bfs
        while (!Q.empty() && !bottleneck[T]) {
            int now = Q.front();
            Q.pop();
            for (int nxt : edge[now]) {
                if (!bottleneck[nxt] && cap[now][nxt] > flow[now][nxt]) {
                    Q.push(nxt);
                    pre[nxt] = now;
                    bottleneck[nxt] = min(bottleneck[now], cap[now][nxt] - flow[now][nxt]);
                }
            }
        }
        if (bottleneck[T] == 0) break;

        for (int now = T; now != S; now = pre[now]) {
            flow[pre[now]][now] += bottleneck[T];
            flow[now][pre[now]] -= bottleneck[T];
        }
        result += bottleneck[T];
    }
    return result;
}