网络流真的博大精深

题意:
在一个迷宫中,新进了一批小蜥蜴. 然而因为一些原因,出口被封住了,而且迷宫燃起了大火,现在小蜥蜴们急着离开,想要求助于ACMer们,哈哈……
把蜥蜴所在的坐标当做一根有高度为k的柱子,现在每有一只蜥蜴跳出格子,格子的柱子高度就会减少一,直到为0,表示这个格子不能在通过蜥蜴. 题目规定,小蜥蜴们可以从当前格子往周围跳出小于等于d距离的长度.当蜥蜴跳出迷宫的边界,就算这只蜥蜴存活下来了,而那些不能逃出去的,就只能等着被烤成烤肉了.现在想要让更多的蜥蜴逃出,求最后剩下的蜥蜴数;

题解:
这道题目有很深的网络流味道…….,具体建模还是基本的网络流模式,就是虚拟出源点和汇点,再把一些相关联的点通过边和流量联系起来. 具体看下我写的代码吧! 里面有解释具体怎么建边.

/* *********************************************** Author :xdlove Created Time :2015年08月18日 星期二 13时18分54秒 File Name :xd.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; /******************************** please don‘t hack me!! /(ToT)/~~ __------__ /~ ~ | //^\\//^\| /~~\ || T| |T|:~ | |6 ||___|_|_||:| \__. / o \/‘ | ( O ) /~~~~\ `\ \ / | |~~\ | ) ~------~` /‘ | | | / ____ /~~~)(_/‘ | | | /‘ | ( | | | | \ / __)/ \ \ \ \/ /‘ \ ` \ \|\ / | |\___| \ | \____/ | | /^~> \ _/ < | | \ | | \ \ -^-\ \ | ) `\_______/^\______/ ************************************/ const int MAXN = 3e3 + 5;//点数的最大值 const int MAXM = 1e6 + 5;//边数的最大值 const int INF = 0x3f3f3f3f; struct Edge { int to,next,cap,flow; } edge[MAXM]; //注意是MAXM int tol; int head[MAXN]; int gap[MAXN],dep[MAXN],cur[MAXN]; void init() { tol = 0; memset(head,-1,sizeof(head)); } void addedge(int u,int v,int w,int rw = 0) { //printf("%d %d %d\n",u,v,w); edge[tol].to = v; edge[tol].cap = w; edge[tol].flow = 0; edge[tol].next = head[u]; head[u] = tol++; edge[tol].to = u; edge[tol].cap = rw; edge[tol].flow = 0; edge[tol].next = head[v]; head[v] = tol++; } int Q[MAXN]; void BFS(int start,int end) { memset(dep,-1,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0] = 1; int front = 0, rear = 0; dep[end] = 0; Q[rear++] = end; while(front != rear) { int u = Q[front++]; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].to; if(dep[v] != -1)continue; Q[rear++] = v; dep[v] = dep[u] + 1; gap[dep[v]]++; } } } int S[MAXN]; int sap(int start,int end,int N) { BFS(start,end); memcpy(cur,head,sizeof(head)); int top = 0; int u = start; int ans = 0; while(dep[start] < N) { if(u == end) { int Min = INF; int inser; for(int i = 0; i < top; i++) if(Min > edge[S[i]].cap - edge[S[i]].flow) { Min = edge[S[i]].cap - edge[S[i]].flow; inser = i; } for(int i = 0; i < top; i++) { edge[S[i]].flow += Min; edge[S[i]^1].flow -= Min; } ans += Min; top = inser; u = edge[S[top]^1].to; continue; } bool flag = false; int v; for(int i = cur[u]; i != -1; i = edge[i].next) { v = edge[i].to; if(edge[i].cap - edge[i].flow && dep[v]+1 == dep[u]) { flag = true; cur[u] = i; break; } } if(flag) { S[top++] = cur[u]; u = v; continue; } int Min = N; for(int i = head[u]; i != -1; i = edge[i].next) if(edge[i].cap - edge[i].flow && dep[edge[i].to] < Min) { Min = dep[edge[i].to]; cur[u] = i; } gap[dep[u]]--; if(!gap[dep[u]])return ans; dep[u] = Min + 1; gap[dep[u]]++; if(u != start)u = edge[S[--top]^1].to; } return ans; } char s[22][22],t[22][22]; struct Point { int x,y,v; Point(){ } Point(int _x,int _y,int _v) { x = _x; y = _y; v = _v; } bool operator == (const Point &a) const { return x == a.x && y == a.y; } }p[MAXN]; int mul(int x) { return x * x; } int dist(Point a,Point b) { return mul(a.x - b.x) + mul(a.y - b.y); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T,kcase = 0; int n,m,d; cin>>T; while(T--) { init(); scanf("%d %d",&n,&d); d *= d; for(int i = 0; i < n; i++) scanf("%s",s[i]); for(int i = 0; i < n; i++) scanf("%s",t[i]); int ss,tt,tot = 0; int num = 0; m = strlen(s[0]); tt = 2 * n * m + 2; ss = tt - 1; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(t[i][j] == ‘L‘) { num++; addedge(ss,i * m + j,1); //对于每只蜥蜴来说,从源点往其建一流量为1的边,表示他能否逃出去; } if(s[i][j] != ‘0‘) { p[tot++] = Point(i,j,i * m + j); addedge(i * m + j,n * m + i * m + j,s[i][j] - ‘0‘);//对于每一个有柱子的格子来说,自己与自己连一条容量为其键值key的边, //表示其最多只能通过key只蜥蜴; } } } //每个格子相互的连边 for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { Point nn = Point(i,j,0); for(int k = 0; k < tot; k++) { int pd = dist(nn,p[k]); if(i == 0 || j == 0 || i == n - 1 || j == m - 1) { if(pd < d) //对于边界点来说,如果距离之和小于d,则当前蜥蜴可以从这个格子逃出; addedge(n * m + p[k].v,tt,INF);//所以往汇点建一条流量为无穷大的边,表示可以从这个格子逃出的蜥蜴数量不确定,取大一点的值; } if(s[i][j] == ‘0‘ || (nn == p[k])) continue;//key=0或者自己,不建边 if(pd <= d) addedge(n * m + p[k].v,i * m + j,INF);//相邻两个格子之间可以通过无穷只蜥蜴,在没有key值限制的情况下; } } } int ans = sap(ss,tt,2 * n * m + 2); ans = num - ans; printf("Case #%d: ",++kcase); if(ans) printf("%d ",ans); else printf("no "); if(ans > 1) printf("lizards were "); else printf("lizard was "); puts("left behind."); } return 0; }

，