「HNOI2007」紧急疏散 - 按时间拆点+动态加点最大流

题目大意

    发生了火警，所有人员需要紧急疏散！假设每个房间是一个$N\times M$的矩形区域。每个格子如果是.，那么表示这是一块空地；如果是X，那么表示这是一面墙，如果是D，那么表示这是一扇门，人们可以从这儿撤出房间。已知门一定在房间的边界上，并且边界上不会有空地。最初，每块空地上都有一个人，在疏散的时候，每一秒钟每个人都可以向上下左右四个方向移动一格，当然他也可以站着不动。疏散开始后，每块空地上就没有人数限制了（也就是说每块空地可以同时站无数个人）。但是，由于门很窄，每一秒钟只能有一个人移动到门的位置，一旦移动到门的位置，就表示他已经安全撤离了。现在的问题是：如果希望所有的人安全撤离，最短需要多少时间？或者告知根本不可能。

---

题目分析

对每个门按照时间拆点，每个时间点只能向汇点流出$1$的流量，将人往对应的点连边跑最大流即可。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

#define pii pair<int,int>
#define mp make_pair

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=8005;

struct Edge {
	int from,to,cap,flow;
	Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
	int n,m,s,t;
	vector<Edge>edges;
	vector<int>G[maxn];
	bool vst[maxn];
	int dist[maxn],cur[maxn],flow;
	void init(int n) {
		this->n=n;
		edges.clear();
		for(int i=1; i<=n; i++)G[i].clear();
	}
	void AddEdge(int x,int y,int v) {
		edges.push_back(Edge(x,y,v,0));
		edges.push_back(Edge(y,x,0,0));
		m=edges.size();
		G[x].push_back(m-2);
		G[y].push_back(m-1);
	}
	bool bfs() {
		memset(vst,0,sizeof(vst));
		memset(dist,0,sizeof(dist));
		queue<int>Q;
		Q.push(t);
		vst[t]=1;
		while(!Q.empty()) {
			int Now=Q.front();
			Q.pop();
			for(int id:G[Now]) {
				Edge& e=edges[id^1];
				int Next=e.from;
				if(!vst[Next]&&e.cap>e.flow) { 
					vst[Next]=1;
					dist[Next]=dist[Now]+1;
					Q.push(Next);
				}
			}
		}
		return vst[s];
	}
	int dfs(int Now,int a) {
		if(Now==t||a==0)return a;
		int flow=0;
		for(int& i=cur[Now]; i<G[Now].size(); i++) {
			Edge& e=edges[G[Now][i]];
			int Next=e.to;
			if(dist[Now]-1!=dist[Next])continue;
			int nextflow=dfs(Next,min(a,e.cap-e.flow));
			if(nextflow>0) {
				e.flow+=nextflow;
				edges[G[Now][i]^1].flow-=nextflow;
				flow+=nextflow;
				a-=nextflow;
				if(a==0)break;
			}
		}
		return flow;
	}
	int maxflow(int s,int t) {
		this->s=s;
		this->t=t;
		while(bfs()) {
			memset(cur,0,sizeof(cur));
			flow+=dfs(s,INT_MAX);
		}
		return flow;
	}
} dinic;

struct QueNode {
	int x,y,t;
};

const int Dirx[]= {0,1,-1,0,0},Diry[]= {0,0,0,1,-1};
int n,m,cnt=0,man=0,ans=0,vst[25][25];
char map[25][25];
vector<pii>vec[405][405];

void Bfs(int Sx,int Sy,int cnt) {
	queue<QueNode>Q;
	memset(vst,0,sizeof(vst));
	Q.push((QueNode) {
		Sx,Sy,0
	});
	vst[Sx][Sy]=1;
	while(!Q.empty()) {
		QueNode Now=Q.front();
		Q.pop();
		vec[cnt][Now.t].push_back(mp(Now.x,Now.y));
		for(int k=1; k<=4; k++) {
			int x=Now.x+Dirx[k],y=Now.y+Diry[k];
			if(vst[x][y]||map[x][y]=='X'||x>n||x<1||y>m||y<1)continue;
			vst[x][y]=1;
			Q.push((QueNode) {
				x,y,Now.t+1
			});
		}
	}
}

int id(int x,int y) {
	return (x-1)*m+y;
}

int id2(int x,int t) {
	return n*m+cnt*(t-1)+x;
}

int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			cin>>map[i][j];
	for(int i=1; i<=n; i++)	
		for(int j=1; j<=m; j++)
			if(map[i][j]=='D')Bfs(i,j,++cnt);
			else if(map[i][j]=='.')man++;
	int S=3*n*m+1,T=3*n*m+2;
	for(int i=1; i<=n; i++)
		for(int j=1; j<=m; j++)
			if(map[i][j]=='.')dinic.AddEdge(S,id(i,j),1);
	bool bj=0;
	for(int t=1; t<=n*m*2; t++) {
		for(int i=1; i<=cnt; i++) {
			dinic.AddEdge(id2(i,t),T,1);
			if(t>1)dinic.AddEdge(id2(i,t-1),id2(i,t),INT_MAX/2);
			for(pii x:vec[i][t])dinic.AddEdge(id(x.first,x.second),id2(i,t),1);
		}
		if(dinic.maxflow(S,T)==man) {
			bj=1;
			printf("%d\n",t);
			break;
		}
	}
	if(!bj)puts("impossible");
	return 0;
}