HDU1733分层最大流

假如说&＃xff0c;16*16 &＃61; 256个位置有255个人和一个门的话&＃xff0c;那么需要255 * 2 &＃43; 1层。显然爆掉。但是这道题据别的大佬题解说也就100层&＃xff0c;并且可以直接分层最大流&＃xff08;100层256满边连接的话&＃xff0c;E &＃61; V &＃61; 2.5e4&＃xff0c;V^2E也会爆掉&＃xff09;。
知道这些就是个水题了&＃xff0c;直接套板子就好&＃xff0c;分层的时候注意下每层的增量就好了。

#include
#include
#include
#include
#include
using namespace std;
const int maxn &＃61; 100010;
const int maxm &＃61; 400010;
const int INF &＃61; 0x3f3f3f3f;
struct edge {int to , next, cap, flow;
}e[maxm];struct ISAP{int n;int tol;int head[maxn];int num[maxn];int dep[maxn], cur[maxn];int q[maxn];int p[maxn];void init(int n){tol &＃61; 0;this-> n &＃61; n;ans &＃61; 0;memset(head, -1, sizeof(head));}void addedge(int u, int v, int c, int rw &＃61; 0){e[tol].to &＃61; v;e[tol].cap &＃61; c;e[tol].flow &＃61; 0;e[tol].next &＃61; head[u];head[u] &＃61; tol &＃43;&＃43;;e[tol].to &＃61; u;e[tol].cap &＃61; rw;e[tol].flow &＃61; 0;e[tol].next &＃61; head[v];head[v] &＃61; tol &＃43;&＃43;;}void bfs(int t){memset(dep, -1, sizeof(dep));memset(num, 0, sizeof(num));num[0] &＃61; 1;int front &＃61; 0;int rear &＃61; 0;dep[t] &＃61; 0;q[rear&＃43;&＃43;] &＃61; t;while(front !&＃61; rear){int u &＃61; q[front &＃43;&＃43;];for(int i &＃61; head[u]; i !&＃61; -1; i &＃61; e[i].next){int v &＃61; e[i].to;if(dep[v] !&＃61; -1)continue;q[rear&＃43;&＃43;] &＃61; v;dep[v] &＃61; dep[u] &＃43; 1;num[dep[v]] &＃43;&＃43;;}}}int ans &＃61; 0;int Maxflow(int s, int t){bfs(t);memcpy(cur, head, sizeof(head));int top &＃61; 0;int u &＃61; s;while(dep[s] < n){if(u &＃61;&＃61; t){int Min &＃61; INF;int inser;for(int i &＃61; 0; i < top; i &＃43;&＃43;){if(Min > e[p[i]].cap - e[p[i]].flow){Min &＃61; e[p[i]].cap - e[p[i]].flow;inser &＃61; i;}}for(int i &＃61; 0; i < top; i &＃43;&＃43;){e[p[i]].flow &＃43;&＃61; Min;e[p[i] ^ 1].flow -&＃61; Min;}top &＃61; inser;u &＃61; e[p[top]^ 1].to;ans &＃43;&＃61; Min;continue;}bool flag &＃61; false;int v;for(int i &＃61; cur[u]; i !&＃61; -1; i &＃61; e[i].next){v &＃61; e[i].to;if(e[i].cap - e[i].flow && dep[v] &＃43; 1 &＃61;&＃61; dep[u]){flag &＃61; true;cur[u] &＃61; i;break;}}if(flag){p[top&＃43;&＃43;] &＃61; cur[u];u &＃61; v;continue;}int Min &＃61; n;for(int i &＃61; head[u]; i !&＃61; -1 ; i &＃61; e[i].next){if(e[i].cap- e[i].flow && dep[e[i].to] < Min){Min &＃61; dep[e[i].to];cur[u] &＃61; i;}}num[dep[u]]--;if(!num[dep[u]]) return ans;dep[u] &＃61; Min &＃43; 1;num[dep[u]] &＃43;&＃43;;if(u !&＃61; s) u &＃61; e[p[--top] ^ 1].to;}return ans;}
}isap;int offsetx[5] &＃61; {0, 1, -1, 0, 0};
int offsety[5] &＃61; {1, 0, 0, -1, 0};
int n, m, u, v, cost;
char tma[20];
int ma[20][20];bool bfs(int x, int y)
{bool vis[20][20] &＃61; {false};queue <int> q;vis[x][y] &＃61; true;q.push(x * 100 &＃43; y);while(!q.empty()){int temp &＃61; q.front();q.pop();int tempx &＃61; temp / 100;int tempy &＃61; temp % 100;if(ma[tempx][tempy] &＃61;&＃61; 2){return true;}vis[tempx][tempy] &＃61; true;for(int i &＃61; 0; i < 4; i &＃43;&＃43;){int tx &＃61; tempx &＃43; offsetx[i];int ty &＃61; tempy &＃43; offsety[i];if(tx >&＃61; 0 && tx < n && ty >&＃61; 0 && ty < m && !vis[tx][ty] && ma[tx][ty] !&＃61; -1){q.push(tx * 100 &＃43; ty);vis[tx][ty] &＃61; true;}}}return false;
}bool judge()
{for(int i &＃61; 0; i < n; i &＃43;&＃43;){for(int j &＃61; 0; j < m; j &＃43;&＃43;){if(ma[i][j] &＃61;&＃61; 1){if(!bfs(i, j)){//cout<return false;}}}}return true;
}
int main() {while(scanf("%d%d", &n, &m) !&＃61; EOF){bool flag &＃61; 0;int tol &＃61; 0;//int s &＃61; 52101;//int t &＃61; 52102;int s &＃61; n * m * 2 * 100 &＃43; 1;int t &＃61; s &＃43; 1;isap.init(t &＃43; 1);const int base &＃61; n * m;for(int i &＃61; 0; i < n; i &＃43;&＃43;){scanf("%s", tma);for(int j &＃61; 0; j < m; j &＃43;&＃43;){if(tma[j] &＃61;&＃61; &＃39;X&＃39;){ma[i][j] &＃61; 1;int temp &＃61; i * m &＃43; j;isap.addedge(s, temp, 1);tol &＃43;&＃43;;}if(tma[j] &＃61;&＃61; &＃39;&＃64;&＃39;){ma[i][j] &＃61; 2;}if(tma[j] &＃61;&＃61; &＃39;#&＃39;){ma[i][j] &＃61; -1;}if(tma[j] &＃61;&＃61; &＃39;.&＃39;){ma[i][j] &＃61; 0;}}}if(!judge()){printf("-1\n");continue;}for(int k &＃61; 0; k <&＃61; 60; k &＃43;&＃43;){for(int i &＃61; 0; i < n; i &＃43;&＃43;){for(int j &＃61; 0; j < m ; j &＃43;&＃43;){if(ma[i][j] &＃61;&＃61; -1)continue;int in &＃61; i * m &＃43; j &＃43; k * base * 2;int out &＃61; in &＃43; base;isap.addedge(in, out, 1);if(ma[i][j] &＃61;&＃61; 2){isap.addedge(out, t, 1);}for(int l &＃61; 0; l < 5; l &＃43;&＃43;){int tempx &＃61; i &＃43; offsetx[l];int tempy &＃61; j &＃43; offsety[l];if(tempx >&＃61; 0 && tempx < n && tempy >&＃61; 0 && tempy < m){if(ma[tempx][tempy] !&＃61; -1){int tin &＃61; tempx * m &＃43; tempy &＃43; (k &＃43; 1) * 2 * base;isap.addedge(out, tin, 1);}}}}}int lll &＃61; isap.Maxflow(s, t);//cout<if( lll &＃61;&＃61; tol){printf("%d\n", k);flag &＃61; 1;break;}}}return 0;
}