HDU 3036 Escape 网格图多人逃生 网络流||二分匹配 建图技巧(二)
.clear(); memset(dis, 0x3f, sizeof(dis)); for (int i = 0; i < r; i++) { scanf("%s", mp[i]); for (int j = 0; j < c; j++) { if (mp[i][j] == 'E') mpe[make_pair(i, j)] = eid++; if (mp[i][j] == '.') mpg[make_pair(i, j)] = gid++; } } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (mp[i][j] == 'E') { bfs(i, j); } } } int L = 1, R = 256, ans = INF; while (L <= R) { int mid = (L + R) >> 1; if (build_and_run(mid)) { ans = mid; R = mid - 1; } else { L = mid + 1; } } if (ans == INF || ans > T) { printf("impossible\n"); } else { printf("%d\n", ans); } } int main() { while (~scanf("%d%d%d", &r, &c, &T)) { memset(g, 0, sizeof(g)); gao(); } return 0; }