UVA 563 Crimewave

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=504

題目大概這樣:
給一個n*m的盤面，和一些格子點
要判斷是否存在一個規劃方法，使得每個點都能走出盤面而不在corner碰撞，
path限定要沿著盤面格子邊邊走。


方法大概這樣: 把每個點當作S，把邊點當作E，每個點限定流量1，每條邊限定流量INF

然後看最大流是否是點的數量

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
#define INF 100000
using namespace std;
typedef long long int int64;
typedef struct _edge{ int a, b, w;}edge;
edge es[100000]; int ecnt = 0; int s = 0, t = 0;
vector<int> link[100000];
int nn = 0;
void init(int n){
ecnt = 0;
for(int lx =0;lx < n;lx++)
link[lx].clear();
nn = n;
return;
}
void addedge(int a, int b, int ab, int ba = 0){
es[ecnt].a = a, es[ecnt].b = b, es[ecnt].w = ab; ecnt++; link[a].push_back(ecnt-1);
es[ecnt].a = b, es[ecnt].b = a, es[ecnt].w = ba; ecnt++; link[b].push_back(ecnt-1);
return;
}
void printes(){
for(int lx = 0;lx < ecnt;lx++){
printf("%d: %d -> %d w = %d\n", lx, es[lx].a, es[lx].b, es[lx].w);
}
printf("--\n");
}
int dis[10000];
int q[10000];
int path[10000];
int post[10000];
int bfs(int s, int t){
//printf("bfs %d->%d\n", s, t);
for(int lx = 0;lx < nn;lx++)
dis[lx] = -1, post[lx] = -1;
int qs = 0, qe = 1;
q[0] = s;
while(qs < qe){
int gg =  q[qs]; qs++;
//printf("bfs at %d\n", gg);
int get_dis = dis[gg];
for(int lx = 0;lx < link[gg].size();lx++){
int ind = es[link[gg][lx]].b;
//printf("ind = %d\n", ind);
if(dis[ind] == -1 and es[link[gg][lx]].w)
q[qe++] = ind, dis[ind] = get_dis + 1, post[ind] = link[gg][lx];
}
//printf("--\n");
}
if(dis[t] == -1)
return 0;
int pathcnt = 0;
int nowg = t;
int min_f = INF;
//printf("A\n");
while(nowg != s){
int rvlinkind = post[nowg];
//printf("%d\n", rvlinkind);
if(rvlinkind == -1) break;
path[pathcnt++] = rvlinkind;
nowg = es[rvlinkind].a;
//printf("nowg = %d\n", nowg);
//for(int ppp = 0;ppp/10000 < 10000;ppp++);
min_f = min(min_f, es[rvlinkind].w);
}
for(int lx = 0;lx < pathcnt;lx++){
int linkind = path[lx];
//printf("link%d\n", linkind);
es[linkind].w -= min_f;
es[linkind^1].w += min_f;
}
return min_f;
}
int Ekarp(int s, int t){
int v = 0;
int mao = 0;
while(1){
v = bfs(s, t);
//printf("%d\n", v);
if(v == 0) break;
mao += v;
}
return mao;
}
int chmap[55][55];
int ss, aa;
int get_index(int x, int y){return y*ss + x;}
int main()
{
int T;scanf("%d", &T);
while(T-->0){
int n;scanf("%d %d %d", &ss, &aa, &n);
init(2*ss*aa + 2);
memset(chmap, 0, sizeof(chmap));
for(int lx = 0;lx < n;lx++){
int p, q;scanf("%d %d", &p, &q);
p--, q--; chmap[p][q] = 1;
}
int sss = 2*ss*aa, eee = 2*ss*aa+1;
for(int lx = 0;lx < ss;lx++)
for(int ly = 0;ly < aa;ly++)
if(chmap[lx][ly] == 0)
addedge(2*get_index(lx, ly), 2*get_index(lx, ly)+1, 1-chmap[lx][ly]);

for(int lx = 0;lx+1 < ss;lx++){
for(int ly = 0;ly < aa;ly++){
addedge(2*get_index(lx, ly)+1, 2*get_index(lx+1, ly), INF);
addedge(2*get_index(lx+1, ly)+1, 2*get_index(lx, ly), INF);
}
}
for(int lx = 0;lx < ss;lx++){
for(int ly = 0;ly+1 < aa;ly++){
addedge(2*get_index(lx, ly+1)+1, 2*get_index(lx, ly), INF);
addedge(2*get_index(lx, ly)+1, 2*get_index(lx, ly+1), INF);
}
}
for(int lx = 0;lx < ss;lx++){
for(int ly = 0;ly < aa;ly++){
if((lx == 0) or (ly == 0) or (lx == ss-1) or (ly == aa-1))
addedge(2*get_index(lx, ly)+1, eee, INF);
if(chmap[lx][ly])
addedge(sss, 2*get_index(lx, ly)+1, 1);
}
}
//printes();
puts(Ekarp(sss, eee) == n ? "possible" : "not possible");
}
return 0;
}