HDU 3036 Escape 网格图多人逃生 网络流||二分匹配 建图技巧(一)

题意：

每个' . '有一个姑娘， 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; queue
        
         q; 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;} vector
         
          E,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; queue
          
           qx,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