題意：
每個' . '有一個姑娘， E是出口，'.'是空地 , 'X‘ 是牆。
每秒鐘每個姑娘可以走一步（上下左右）
每秒鐘每個出口只能出去一個人
給定n*m的地圖， 時限T
問所有姑娘能否在T秒內逃生，若能輸出最小值，不能輸出"impossible"
思路：
顯然是二分答案+網絡流判可行。
因為每個出口每秒鐘只能出去一個人，那麼就把每個出口按時間拆點，則T秒鐘就拆成T個點。
網絡流建圖
1、源點 到 每個姑娘 建流量為1的邊。
2、若某姑娘到 a出口需要時間為 t秒，則建一條流量為1的邊 連向a出口拆點為t秒的點。
3、每個出口的所有拆點向匯點連一條流量為1的邊。
4、對於每個出口u的x秒拆點，向u的x+1秒的拆點連一條流量為inf的邊（表示從x秒來的人如果x秒還從u出不去，可以在u等到x+1秒出去）
二分一下 第二點中的 t 秒(即答案），判斷最大流是否等於人數
二分匹配建圖：
枚舉時間（因為時間最大只有12*12）
在原圖的基礎上加上下面的邊：
在i時間內若能出去則那姑娘向所有能出去的 出口時間拆點連邊。
再在原來的匹配上繼續增廣，累計最大匹配數。
當最大匹配數==人數時則是最小的時間。
數據較水可以用點非主流的建圖卡過去，估計只有30組數據。
網絡流代碼：
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll int
#define N 20050
#define M 105000
#define inf 10737418
struct Edge{
ll from, to, cap, nex;
}edge[M*4];//注意這個一定要夠大 不然會re 還有反向弧
ll head[N], edgenum;
void add(ll u, ll v, ll cap){
Edge E = { u, v, cap, head[u]};
edge[ edgenum ] = E;
head[u] = edgenum ++;
Edge E2= { v, u, 0, head[v]};
edge[ edgenum ] = E2;
head[v] = edgenum ++;
}
ll sign[N];
bool BFS(ll from, ll to){
memset(sign, -1, sizeof(sign));
sign[from] = 0;
queueq;
q.push(from);
while( !q.empty() ){
int u = q.front(); q.pop();
for(ll i = head[u]; i!=-1; i = edge[i].nex)
{
ll v = edge[i].to;
if(sign[v]==-1 && edge[i].cap)
{
sign[v] = sign[u] + 1, q.push(v);
if(sign[to] != -1)return true;
}
}
}
return false;
}
ll Stack[N], top, cur[N];
ll dinic(ll from, ll to){
ll ans = 0;
while( BFS(from, to) )
{
memcpy(cur, head, sizeof(head));
ll u = from; top = 0;
while(1)
{
if(u == to)
{
ll flow = inf, loc;//loc 表示 Stack 中 cap 最小的邊
for(ll i = 0; i < top; i++)
if(flow > edge[ Stack[i] ].cap)
{
flow = edge[Stack[i]].cap;
loc = i;
}
for(ll i = 0; i < top; i++)
{
edge[ Stack[i] ].cap -= flow;
edge[Stack[i]^1].cap += flow;
}
ans += flow;
top = loc;
u = edge[Stack[top]].from;
}
for(ll i = cur[u]; i!=-1; cur[u] = i = edge[i].nex)//cur[u] 表示u所在能增廣的邊的下標
if(edge[i].cap && (sign[u] + 1 == sign[ edge[i].to ]))break;
if(cur[u] != -1)
{
Stack[top++] = cur[u];
u = edge[ cur[u] ].to;
}
else
{
if( top == 0 )break;
sign[u] = -1;
u = edge[ Stack[--top] ].from;
}
}
}
return ans;
}
void init(){memset(head,-1,sizeof head);edgenum = 0;}
char mp[15][15];
int n, m, T;
int Hash(int x,int y){return x*m+y;}
vectorE,P;
int dis[150][150], step[4][2]={1,0,-1,0,0,1,0,-1};
bool vis[150][150];
void bfs(int sx,int sy){
int start = Hash(sx,sy);
memset(vis, 0, sizeof vis);
vis[sx][sy] = 1;
dis[start][start] = 0;
queueqx,qy; while(!qx.empty())qx.pop(); while(!qy.empty())qy.pop();
qx.push(sx), qy.push(sy);
while(!qx.empty()){
int x = qx.front(), y = qy.front();
qx.pop(); qy.pop();
for(int i = 0; i < 4; i++){
int dx = x + step[i][0], dy = y + step[i][1];
if(!(0<=dx&&dx>1;
if(ok(mid))ans = min(ans, mid), r = mid-1;
else l = mid+1;
}
if(T二分匹配代碼：
#include
#include
