HDU 1733 escape(最大流 + dinic算法)

/*
超时，不过不想找错误了！做这道题开始接触dinic算法
如果想要学dinic算法，参见：
http://wenku.baidu.com/view/98deaf06b52acfc789ebc91a.html###
http://www.cnblogs.com/ltang/archive/2010/11/17/1879573.html

题意：
X代表人，@代表教室门，问所有的人都跑出教室需要多久，每次只能走一步而且所走位置不能有人。

题解：最大流 + dinic算法
具体构图如下：
A: 增加源点src，和汇点dest，然后根据每个时间点建出分层图，每个时间对应一层，对于每层图的构造如下
B:给每个格子标上号Xi， 由于每个格子一次只能占一人，所以把每个格子分为两个点xa，xb，连上容量为1的有向边，对于格子为‘X’的，（如果为第0层的话）在源点src与xa之间连一条容量为1的有向边，对于格子为'@'的点，在xb与汇点dest连上容量为1的有向边，对于每个格子，（除‘#’外），在xb与其上下左右及其本身 的对应下一层图的xa连上容量为1 的一条有向边
C:具体操作并不是一下子建出分层图，由于时间是未知的，所以枚举时间，做最大流，当最大流小于人数时，时间加一并在原图上增加一层，继续求最大流，直到最大流大于等于人数，这时的时间就是答案
*/

#include <iostream>
#define re(i, n) for(int i = 0; i < n; ++ i)
using namespace std;

const int Max = 20;
const int nMax = 320000;
const int mMax = 3200000;
const int INF = 0x7fffffff;
char map[Max][Max];
int mark[Max][Max];
int d[Max][Max];

int qx[nMax], qy[nMax], k;
struct Edge
{
	int v, w, next;
	Edge(){}
	Edge(int v, int w, int next): v(v), w(w), next(next){}
}adj[mMax];
int head[nMax], ind;
int dis[nMax];
int queue[nMax];

int dir[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int num, node, z;
int s, t;
int n, m;
int MaxFlow;

void buildDi(int _k)//这个函数主要对矩阵进行处理，能够到门口的所有节点都满足d[i][j] != 0，便于判断是否存在无论如何也出不去的同学
{
	memset(d, -1, sizeof(d));
	for(int i = 0; i < _k; ++ i)
		d[qx[i]][qy[i]] = 0;
	for(int i = 0; i < _k; ++ i)
	{
		for(int j = 0; j < 4; ++ j)
		{
			int x = qx[i] + dir[j][0];
			int y = qy[i] + dir[j][1];
			if(x >= 0 && x < n && y >= 0 && y < m && map[x][y] != '#' && d[x][y] == -1)
			{
				d[x][y] = d[qx[i]][qy[i]] + 1;
				qx[_k] = x;
				qy[_k] = y;
				_k ++;//对qx[]，qy[]不断补充节点
			}
		}
	}
}

bool ok()//判断X与@是否可通
{
	re(i, n) re(j, m)
	{
		if(map[i][j] == 'X' && d[i][j] < 0) return 0;
	}
	return 1;
}

void addEdge(int u, int v, int w)
{
	adj[ind] = Edge(v, w, head[u]);
	head[u] = ind ++;
	adj[ind] = Edge(u, 0, head[v]);
	head[v] = ind ++;
}

void makeGraph()//每当时间增加1，则增加一层，建图参见上面详细介绍
{
	node += 2 * z;
	re(i, n) re(j, m)
		if(mark[i][j])
		{
			addEdge(node + mark[i][j], node + mark[i][j] + z, 1);
			addEdge(node + mark[i][j] - z, node + mark[i][j], 1);
			if(map[i][j] == '@') addEdge(node + mark[i][j] + z, t, 1);
			for(int k = 0; k < 4; ++ k)
			{
				int x = i + dir[k][0];
				int y = j + dir[k][1];
				if(x >= 0 && x < n && y >= 0 && y < m && mark[x][y])
				addEdge(node + mark[x][y] - z, node + mark[i][j], 1);
			}
		}
}

int dinicBfs()//dinic算法中建层次图的部分，同时判断是否存在可行弧
{
	memset(dis, -1, sizeof(dis));
	int rear, front;
	front = rear = 0;
	queue[rear ++] = s;
	dis[s] = 0;
	while(front < rear)
	{
		int u = queue[front ++];
		for(int id = head[u]; id != -1; id = adj[id].next)
		{
			int v = adj[id].v;
			if(adj[id].w && dis[v] == -1)
				//这里条件判断有疑问，因为这里建立层次图的目的是为了dinicDfs()可以查找到一条最短最广路，所以dis[v]之前应该没有被访问过
			{
				dis[v] = dis[u] + 1;
				if(v == t) return 1;
				queue[rear ++] = v;
			}
		}
	}
	return 0;
}

int dinicDfs(int cur, int cost = INF)//查找最短增广路径
{
	if(cur == t) return cost;
	int low;
	int ans = 0;
	for(int id = head[cur]; id != -1; id = adj[id].next)//这里其实并不只是寻找了一条增广路径，多条进行了汇合
	{
		int v = adj[id].v;
		if(adj[id].w && (dis[v] == dis[cur] + 1) && (low = dinicDfs(v, min(adj[id].w ,cost))))
		{
			adj[id].w -= low;
			adj[id ^ 1].w += low;
			ans += low;//各条增广路径最大流量之和
			cost -= low;//剩余可用流量
			if(!cost) break;
		}
	}
	return ans;
}

int dinicFlow()//dinic算法，输出最大流，因为题中特殊条件，所以MaxFlow需要定义成全局变量，并进行累加
{
	while(dinicBfs())
		MaxFlow += dinicDfs(s);
	return MaxFlow;
}

int main()
{
	//freopen("e://data.in", "r", stdin);
	while(scanf("%d %d", &n, &m) != EOF)
	{
		num = 0;
		k = 0;
		z = 0;
		re(i, n)
		{
			getchar();
			re(j, m)
			{
				map[i][j] = getchar();
				if(map[i][j] != '#') mark[i][j] = ++z;//每一层的节点数
				else mark[i][j] = 0;
				if(map[i][j] == '@') qx[k] = i, qy[k] = j, ++k;//存储教室门的坐标
				if(map[i][j] == 'X') ++num;//总人数
			}
		}
		buildDis(k);
		if(!ok())
		{
			printf("-1\n");
			continue;
		}
		s = 0;
		t = 1;
		node = 1;
		ind = 0;
		memset(head, -1, sizeof(head));
		re(i, n) re(j, m)
		{
			if(mark[i][j])
			{
				if(map[i][j] == 'X') addEdge(s, mark[i][j] + node, 1);
				addEdge(mark[i][j] + node, mark[i][j] + node + z, 1);
			}
		}
		int ans = 0;
		MaxFlow = 0;
		while(dinicFlow() < num) 
		{
			makeGraph();
			ans++;
		}
		printf("%d\n", ans);
	}
	return 0;
}