sb错误调了3hour+。。
bfs预处理出每个
\(.\)到每个
\(D\)的最短距离。
二分时间
\(t\)，把每个
\(D\)拆成
\(t\)个点，这
\(t\)个点两两连边，流量
\(INF\)表示
\(t\)个时刻都可以从这个
\(D\)出。
然后枚举所有
\(.\)，再枚举所有
\(D\)，如果距离
\(dis\)小于
\(t\)，就从这个
\(.\)向这个
\(D\)的第
\(dis\)个点连一条流量为
\(1\)的边，表示从这个时刻开始这个
\(.\)可以从这个
\(D\)出。
然后求最大流，如果等于
\(.\)的个数，说明此
\(t\)可行，二分一下即可。
#include #include #include #include #define INF 2147483647using namespace std;const int MAXN = 300010;const int N = 440;const int MAXM = 200010;char a[N][N];int b[N][N], c[N][N];struct point{ int x, y, time;}Now;queue q;queue Q;struct Edge{ int from, to, next, rest;}e[MAXM];int head[MAXN], num = 1, s, t, now, n, m, dis[MAXN];inline void Add(int from, int to, int flow){ e[++num] = (Edge){ from, to, head[from], flow }; head[from] = num; e[++num] = (Edge){ to, from, head[to], 0 }; head[to] = num;}inline int id(int i, int j){ return (i - 1) * m + j;}int re(){ memset(dis, 0, sizeof dis); q.push(s); dis[s] = 1; while(q.size()){ now = q.front(); q.pop(); for(int i = head[now]; i; i = e[i].next) if(e[i].rest && !dis[e[i].to]) dis[e[i].to] = dis[now] + 1, q.push(e[i].to); } return dis[t];}int find(int u, int flow){ if(u == t || !flow) return flow; /*if(u == 448){ int xsxs = 1; }*/ int sum = 0, T; for(int i = head[u]; i; i = e[i].next) if(e[i].rest && dis[e[i].to] == dis[u] + 1){ T = find(e[i].to, min(flow - sum, e[i].rest)); e[i].rest -= T; e[i ^ 1].rest += T; sum += T; } if(!sum) dis[u] = 0; return sum;}int dinic(){ int ans = 0; while(re()) ans += find(s, INF); /*for(int i = 1; i <= num; ++i) if(e[i].to <= n * m && e[i].from == s) if(e[i].rest) printf("%d %d %d\n", (e[i].to - 1) / 12 + 1, e[i].to % 12 == 0 ? 12 : e[i].to % 12, e[i].to); system("pause");*/ return ans;}int cnt, tot, l[] = {233, -1, 1, 0, 0}, r[] = {666, 0, 0, -1, 1}, vis[N][N], L, R;void bfs(int x, int y){ Q.push((point){x, y, 0}); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) vis[i][j] = 0; vis[x][y] = 1; while(Q.size()){ Now = Q.front(); Q.pop(); for(int i = 1; i <= 4; ++i){ int X = Now.x + l[i], Y = Now.y + r[i]; if(!X || !Y || X > n || Y > m || a[X][Y] == 'X' || vis[X][Y]) continue; Q.push((point){X, Y, Now.time + 1}); vis[X][Y] = 1; if(b[X][Y]) c[id(x, y)][b[X][Y]] = Now.time + 1; } }}int ans, mid;int main(){ scanf("%d%d", &n, &m); s = 290000; t = 300001; for(int i = 1; i <= n; ++i) scanf("%s", a[i] + 1); for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(a[i][j] == 'D') b[i][j] = ++cnt; else if(a[i][j] == '.') ++tot; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(a[i][j] == '.') bfs(i, j); L = 1; R = 400; ans = -1; if(tot) while(L <= R){ mid = (L + R) >> 1; memset(head, 0, sizeof head); num = 1; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) if(a[i][j] == '.'){ Add(s, id(i, j), 1); for(int k = 1; k <= cnt; ++k){ int d = id(i, j); if(c[d][k] && c[d][k] <= mid) Add(d, 400 + cnt * c[d][k] + k, 1); } } for(int i = 1; i <= cnt; ++i) for(int j = 1; j <= mid; ++j) Add(400 + cnt * j + i, t, 1), Add(400 + cnt * j + i, 400 + cnt * j + cnt + i, INF); if(dinic() == tot) ans = mid, R = mid - 1; else L = mid + 1; } if(ans == -1) printf("impossible\n"); else printf("%d\n", ans); return 0;}