UVa 563 - Crimewave

题目分析

因为每个点有限制，很容易想到拆点，然后求最大流判断是否等于b即可。现在已经很容易手打ISAP网络流算法了。。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1e5+100;
const int maxm = 1e6+100;
const int INF = 0x3f3f3f3f;

struct Edge{
    int to, cap, next;
}e[maxm<<1];
int head[maxn], tot;
int num[maxn], d[maxn], pre[maxn], cur[maxn];
int sink, source, nv;
int s, a, b;

void addedge(int from, int to){
    e[tot].to = to;
    e[tot].cap = 1;
    e[tot].next = head[from];
    head[from] = tot++;

    e[tot].to = from;
    e[tot].cap = 0;
    e[tot].next = head[to];
    head[to] = tot++;
}

void rev_bfs(){
    memset(num, 0, sizeof(num));
    memset(d, -1, sizeof(d));
    d[sink] = 0;
    num[0] = 1;
    queue <int> q;
    q.push(sink);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u]; i != -1; i = e[i].next){
            int v = e[i].to;
            if(d[v] != -1) continue;
            d[v] = d[u] + 1;
            q.push(v);
            num[d[v]]++;
        }
    }

}

int ISAP(){
    memcpy(cur, head, sizeof(cur));
    rev_bfs();
    int flow = 0, u = pre[source] = source, i;
    while(d[source] < nv){
        if(u == sink){
            int f = INF, neck;
            for(i = source; i != sink; i = e[cur[i]].to)
                if(f > e[cur[i]].cap){
                    f = e[cur[i]].cap;
                    neck = i;
                }
            for(i = source; i != sink; i = e[cur[i]].to){
                e[cur[i]].cap -= f;
                e[cur[i]^1].cap += f;
            }
            flow += f;
            u = neck;  //记录应该回退的点,不直接回退到源点，小优化
        }
        for(i = cur[u]; i != -1; i = e[i].next)  //找最短路
            if(d[e[i].to] + 1 == d[u] && e[i].cap) break;
        if(i != -1){
            cur[u] = i;  //记录当前弧
            pre[e[i].to] = u; //记录上一个节点
            u = e[i].to;
        }
        else{  //u到sink出现断层
            if(0 == (--num[d[u]])) break; //GAP间隙优化，如果出现断层，可以知道一定不会再有增广路了
            int mind = nv;
            for(i = head[u]; i != -1; i = e[i].next)
                if(e[i].cap && mind > d[e[i].to]){
                    cur[u] = i;   //修改当前弧
                    mind = d[e[i].to];
                }
            d[u] = mind+1;
            num[d[u]]++;
            u = pre[u];  //回退到上一个点
        }
    }
    return flow;
}

bool judge(int x, int y){
    if(x < 1 || x > s || y < 1 || y > a) return false;
    return true;
}

void init(){
    memset(head, -1, sizeof(head));
    tot = 0;
}

void solve(){
    init();
    scanf("%d%d%d", &s, &a, &b);
    for(int i = 1; i <= s; i++){
        for(int j = 1; j <= a; j++){
            int loc = (i-1)*a+j;
            addedge(loc, loc+s*a);
            if(judge(i+1, j)){
                addedge(i*a+j+s*a, loc);
                addedge(loc+s*a, i*a+j);
            }
            if(judge(i, j+1)){
                addedge((i-1)*a+j+1+s*a, loc);
                addedge(loc+s*a, (i-1)*a+j+1);
            }
            if(i == 1 || j == 1 || i == s || j == a){
                addedge(loc+s*a, 2*s*a+1);
            }
        }
    }
    int x, y;
    for(int i = 1; i <= b; i++){
        scanf("%d%d", &x, &y);
        int loc = (x-1)*a+y;
        addedge(0, loc);
    }
    source = 0, sink = 2*s*a+1;
    nv = sink+1;
    printf(b == ISAP() ? "possible\n" : "not possible\n");
}

int main(){
    int T;
    scanf("%d", &T);
    while(T--) solve();
    return 0;
}