首页 > ACM题库 > HDU-杭电 > hdu 2644 Escape[解题报告]hoj
2014
02-12

hdu 2644 Escape[解题报告]hoj

Escape

问题描述 :

One night , when dandelion fell asleep , she finds herself in a big maze . Different with other mazes ,the exit of the maze is changing all the time . Now dandelion knows the maze is made up of N rooms , signed as 1,2 …n. Some of the rooms are connected with undirected ways . To escape from the maze as soon as possible , every time dandelion will move to the room which is nearest to the exit . If there are several rooms , she will choose the room with the smallest number .Meanwhile , to leave the maze more quickly ,during every unit time , after moving once if dandelion doesn’t reach the exit ,she can move once again . If dandelion still doesn’t reach the exit , the exit will move to any room that connected with it , or stay at the same room . The possibility is average . Now dandelion wants to know the average time she needs to escape from the maze. Can you help her?

输入:

There are several cases ,every case begins with two numbers n and m (1<=n,m<=1000),stands for the number of rooms and the number of the ways . The second line contains two numbers a and b ,stands for the room where dandelion and the exit exist at the beginning . Then m lines ,each line with two numbers p and q ,stands for there is a way between room p and room q.

输出:

There are several cases ,every case begins with two numbers n and m (1<=n,m<=1000),stands for the number of rooms and the number of the ways . The second line contains two numbers a and b ,stands for the room where dandelion and the exit exist at the beginning . Then m lines ,each line with two numbers p and q ,stands for there is a way between room p and room q.

样例输入:

4 3
1 4
1 2
2 3
3 4
2 1
1 1
1 2

样例输出:

1.500
0.000

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 121111
#define M 600000
#define inf 0x7fffffff
char map[20][20];

struct node {
	int to, next, c;
} edge[M];
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

int edgehead[N], now[N], dis[N];
int que[M];
int n, m, s, t, cnt, d, w;
int door, pos;

struct node2 {
	int x, y;
} p[800], q[800];

void addedge(int u, int v, int c) {
	edge[cnt].to = v, edge[cnt].c = c, edge[cnt].next = edgehead[u];
	edgehead[u] = cnt++;
	edge[cnt].to = u, edge[cnt].c = 0, edge[cnt].next = edgehead[v];
	edgehead[v] = cnt++;
}

void init() {
	memset(edgehead, -1, sizeof (edgehead));
	cnt = 0;
}

bool find_path(int s, int t) {
	for (int i = 0; i <= t; i++) {
		dis[i] = inf;
		now[i] = -1;
	}
	int head = 0, tail = 1;
	que[head] = s;
	dis[s] = 0;
	while (head <= tail) {
		int cur = que[head++];
		if (dis[t] <= dis[cur])break;
		for (int i = edgehead[cur]; i != -1; i = edge[i].next)if (edge[i].c > 0) {
				int v = edge[i].to;
				if (now[cur] == -1)
					now[cur] = i;
				if (dis[v] == inf) {
					dis[v] = dis[cur] + 1;
					que[tail++] = v;
				}
			}
	}
	return dis[t] != inf;
}

int dfs(int s, int t, int nowflow) {
	if (s == t) return nowflow;
	int flow = 0;
	int i;
	for (i = now[s]; i != -1; i = edge[i].next)if (edge[i].c > 0 && dis[edge[i].to] == dis[s] + 1) {
			int temp = dfs(edge[i].to, t, min(nowflow - flow, edge[i].c));
			edge[i].c -= temp;
			edge[i^1].c += temp;
			flow += temp;
			if (flow == nowflow)
				break;
		}
	now[s] = i;
	return flow;
}

int maxflow(int s, int t) {
	int flow = 0;
	while (find_path(s, t))flow += dfs(s, t, inf);
	return flow;
}

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

int getid1(int num, int time) {
	return n * m * time * 2 + 2 * num - 1;
}

int getid2(int num, int time) {
	return (n * m)*time * 2 + 2 * num;
}

bool isok(int x, int y) {
	if (x >= 1 && x <= n && y >= 1 && y <= m && map[x][y] != '#')
		return 1;
	return 0;
}

void build(int mid) {
	s = 0, t = 2 * (n * m)*(mid + 5) + 5;
	for (int i = 1; i <= pos; i++) {
		int id = getid(q[i].x, q[i].y);
		int id1 = getid1(id, 0);
		addedge(s, id1, 1);
	}
	for (int i = 1; i <= door; i++)
		for (int time = 0; time <=mid; time++) {
			int id = getid(p[i].x, p[i].y);
			int id2 = getid2(id, time);
			addedge(id2, t, 1);
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (map[i][j] != '#')
				for (int time = 0; time <= mid; time++) {
					int id = getid(i, j);
					int id1 = getid1(id, time);
					int id2 = getid2(id, time);
					addedge(id1, id2, 1);
				}
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			if (map[i][j] != '#')
				for (int de = 0; de < 4; de++) {
					int newx = i + dx[de];
					int newy = j + dy[de];
					if (isok(newx, newy)) {
						for (int time = 0; time < mid; time++) {
							int id = getid(i, j);
							int id1 = getid(newx, newy);
							int id3 = getid2(id, time);
							int id4 = getid1(id1, time + 1);
							int id5=getid1(id,time+1);
							addedge(id3, id4, inf);
							addedge(id3,id5,inf);
						}
					}
				}
		}
}

int main() {
	while (scanf("%d%d", &n, &m) != EOF) {
		for (int i = 1; i <= n; i++)
			scanf("%s", &map[i][1]);
		door = 1, pos = 1;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) {
				if (map[i][j] == '@') {
					p[door].x = i;
					p[door].y = j;
					door++;
				}
				if (map[i][j] == 'X') {
					q[pos].x = i;
					q[pos].y = j;
					pos++;
				}
			}
		door--, pos--;
		int l = 1, r = n*m+1, ans = -1;
		while (l <= r) {
			init();
			int mid = (l + r) / 2;
			build(mid);
			int cur = maxflow(s, t);
			if (cur == pos) {
				r = mid - 1;
				ans = mid;
			}
			else
				l = mid + 1;
		}
		printf("%d\n",ans);
	}
	return 0;
}

  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢