2014
02-12

# 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 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];
edge[cnt].to = u, edge[cnt].c = 0, edge[cnt].next = edgehead[v];
}

void init() {
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;
dis[s] = 0;
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);
}
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);
}
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);
}
}
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);
}
}
}
}
}

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也帮想想, 有想法欢迎来邮件。谢谢