uva 563 - Crimewave（网络流最大流） - c++编程基础

题目大意:在一个r*c的城市中，有n个银行，有一个抢匪想抢劫这n家银行，每次抢劫后需逃离城市（移动到坐标外），但是又不能走先前走过的位置，给出n个银行的坐标，问说抢匪能非成功抢劫银行并且逃脱。

解题思路：很经典的逃脱问题，要不是因为在刷网络流的专题根本想不到要用网络流去做。

首先先讲每个点与它周围的4个点建立一条边，表示可以移动。（注意要拆点，因为每个点都有容量限制，即只能走过一次，所以对于点c，要建立一个c‘，c’指向c有一条容量大小为1的边，所有与c点有关的点所建立的边统统指向c‘，而c点指向其他点的边任然保留在c上）

其次是建立汇点t，将所有的边界点指向汇点。

然后读入n个银行的坐标，对应的建立起点s与银行间的边。

最后是最大流问题，计算出从起点s到汇点t的最大流值ans，若ans等于n，说明成功，否则失败。

昨天晚上做一一晚上这道题目，一直RE，最后到会宿舍才发现说在拆点的时候，c ->c’ = c + T； T = R * C才对，应该是2500，但我一直以为是250，郁闷啊~

还有这道题应该用邻接表的来储存关系，不过因为做得太纠结，就懒得改了，数组开太大，时间有点久。

#include   
#include   
#include   
  
#define min(a,b) (a)<(b) (a):(b)  
#define max(a,b) (a)>(b) (a):(b)  
  
using namespace std;  
  
const int N = 5010;  
const int T = 2500;  
const int INF = 1 << 20;  
const int dir[10][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };  
  
int r, c, n, tmp;  
int p[N][N], f[N][N];  
int g[N][T + 10], son[N];  
  
void add(int x, int y) {  
    p[x][y] = 1;  
    g[x][son[x]++] = y;  
}  
  
void init() {  
  
    memset(g, 0, sizeof(g));  
    memset(son, 0, sizeof(son));  
  
    memset(p, 0, sizeof(p));  
    memset(f, 0, sizeof(f));  
  
    scanf("%d%d%d", &r, &c, &n);  
    tmp = 5001;  
  
    for (int i = 1; i <= r; i++) {  
  
        for (int j = 1; j <= c; j++) {  
  
            if (i == 1 || j == 1 || i == r || j == c)  
                add( (i-1) * c + j, 0);  
  
            add( (i-1) * c + j + T, (i-1) * c + j);  
  
            for (int k = 0; k < 4; k++) {  
  
                int p = i + dir[k][0], q = j + dir[k][1];  
  
                if (p <= 0 || p >




 r) continue;  
                if (q <= 0 || q > c) continue;  
  
                add( (i-1) * c + j, (p-1) * c + q + T);  
            }  
        }  
    }  
  
    int a, b;  
    for (int i = 0; i < n; i++) {  
  
        scanf("%d%d\n", &a, &b);  
        add(tmp, (a-1) * c + b + T);      
    }  
}  
  
int solve() {  
    int ans = 0;  
    int k, s[N], path[N];  
    queue que;  
  
    while (1) {  
  
        memset(path, 0, sizeof(path));  
        memset(s, 0, sizeof(s));  
  
        path[tmp] = tmp;  
        s[tmp] = INF;  
        que.push(tmp);  
  
        while (!que.empty() ) {  
            k = que.front(), que.pop();  
  
            for (int i = 0; i < son[k]; i++) {  
  
  
                if ( !s[g[k][i]] && p[k][g[k][i]] > f[k][g[k][i]]) {  
  
                    s[g[k][i]] = min(s[k], p[k][g[k][i]] - f[k][g[k][i]]);  
                    path[g[k][i]] = k;  
                    que.push(g[k][i]);  
                }  
            }  
        }  
  
        if (s[0] == 0) break;  
  
        ans += s[0];  
        for (int i = 0; i != tmp; i = path[i]) {  
            f[path[i]][i] += s[0];  
            f[i][path[i]] -= s[0];  
        }  
    }  
    return ans;  
}  
  
int main () {  
    int cas;  
    scanf("%d", &cas);  
    while (cas--) {  
        init();  
  
        int ans = solve();  
        printf("%s\n", ans == n   "possible" : "not possible");  
    }  
    return 0;  
}