该来的总是会来的，写一道最头痛的网络流问题。
Problem Description
Loneknight hates attending class very much. Every time he is attending class, when he feel tiresome with the class, he start planning the shortest path he can escape from the classroom. Therefore, he can escape from classroom so quickly that he is always the first one escape from the classroom after the class finishes. He is very proud of this fact.
One day, loneknight is day dreaming in class, and planning the shortest path for escaping. Suddently, an issue come into his mind, if everyone in the classroom want to escape as soon as possible just as loneknight, what will happend? As a kind man, loneknight want to plan a strategy that will let everyone escape from the classroom with minimum time consume. But after dozens of minutes of consideration, loneknight find this problem so difficult for him.
Now, as the best friend of him, please design a algorithm to solve this problem for him. Note that, at every time unit, everyone can move seperately up, down, left, right one unit, or stay in the old position. In addtion, no one can move to a wall or out of the room, the only way to escape is go through a gate. Moreover, at every time unit, a position can only contain a person, including gates. That means if in time t, a person escape thourgh gate g, no one can go into g in time t, but can go into g in t + 1. Now, it’s your job to calculate the minimum time required to escape for everyone.
Input
The input consists of several test cases. Each test case start with a line containing two number, n, m (1
通过网络流+枚举时间解决。
题目大意：输入一个n*m的矩阵，表示一个迷宫，其中用#表示墙壁，@表示出口，X表示人， . 表示通道。人每分钟只能够移动一格。求所有人走到出口的最短时间。无解输出-1.
解题思路：
首先通过DFS判断是否有解。
拆点，对于第d分钟，每个点已被拆为d+1个点，下标代号存成等差数列的形式。
起始时，s向第0分钟的n*m中是人的点连条权值为1的边。
而后从小到大枚举每分钟，假设第t分钟，那么对于t-1分钟的点可以向四周扩展，或不动，向对应在第t分钟新加的点连条权为1的边，然后对第t分钟的n*m点，如果是出口则向汇点连条权值为1的边，然后从源点到汇点做网络流，如果ans等于人数，则break，return t。
参考代码：
#include
#include
#include
char mp[30][30];
int cnt,ans,head[30000],gap[30000],dis[30000],sum,vi[30][30];
const int inf=1=1&&x=1&&y0&&dis[x]==dis[y]+1)
{
int temp_flow=gfs(y,min(temp,c));
temp-=temp_flow;
edge[j].f-=temp_flow;
edge[j^1].f+=temp_flow;
if(temp==0||dis[s]==nn)
return flow-temp;
}
if(c>0&&pos>dis[y])
pos=dis[y];
}
if(temp==flow)
{
if(!(--gap[dis[x]]))
dis[s]=nn;
else
gap[dis[x]=pos+1]++;
}
return flow-temp;
}
int sap()
{
int maxflow=0;
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
gap[0]=nn;
while(dis[s]
最头痛的就是网络流问题了。比赛的时候从来都是放到最后做，于是就从来也没有做过。这道题很多地方是直接套了模板。还借鉴了菊苣的解题报告。这篇网络流入门的文章写的很好~
参考报告：HDU 1733 Escape（分层网络流）、HDU 1733 Escape 分层图网络流+枚举时间（这篇写的很详细）