題面

題解

\(\text{HNOI2007}\)真的恐怖

這是集合了所羅門的咒語，勝負一子等神仙題和碼農題的一年

所以這道題非常碼

二分答案，將門拆點，于是就變成了一個二分圖匹配的題目

反正很惡心

代碼

#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> #include<queue> #define RG register #define file(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout); #define clear(x, y) memset(x, y, sizeof(x))inline int read() {int data = 0, w = 1; char ch = getchar();while(ch != '-' && (!isdigit(ch))) ch = getchar();if(ch == '-') w = -1, ch = getchar();while(isdigit(ch)) data = data * 10 + (ch ^ 48), ch = getchar();return data * w; }const int N(25), INF(0x3f3f3f3f); const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; int n, m; char g[N][N];namespace DINIC {const int maxn(5e4 + 10), maxm(1e6 + 10);struct edge { int next, to, cap; } e[maxm];int head[maxn], e_num = -1, S, T, q[maxn], tail, lev[maxn], cur[maxn];inline void add_edge(int from, int to, int cap){e[++e_num] = (edge) {head[from], to, cap}; head[from] = e_num;e[++e_num] = (edge) {head[to], from, 0 }; head[to] = e_num;}int bfs(){clear(lev, 0); q[tail = lev[S] = 1] = S;for(RG int i = 1; i <= tail; i++){int x = q[i];for(RG int j = head[x]; ~j; j = e[j].next){int to = e[j].to;if(lev[to] || (!e[j].cap)) continue;lev[q[++tail] = to] = lev[x] + 1;}}return lev[T];}int dfs(int x, int f){if(x == T || (!f)) return f;int ans = 0, cap;for(RG int &i = cur[x]; ~i; i = e[i].next){int to = e[i].to;if(e[i].cap && lev[to] == lev[x] + 1){cap = dfs(to, std::min(f - ans, e[i].cap));e[i].cap -= cap, e[i ^ 1].cap += cap, ans += cap;if(ans == f) break;}}return ans;}inline int main(){int ans = 0;while(bfs()){for(RG int i = S; i <= T; i++) cur[i] = head[i];ans += dfs(S, INF);}return ans;} }std::vector<int> dX, dY, pX, pY; int dis[N][N][N][N];void BFS(int x, int y, int d[N][N]) {std::queue<int> qx, qy;d[x][y] = 0; qx.push(x), qy.push(y);while(!qx.empty()){x = qx.front(); qx.pop();y = qy.front(); qy.pop();for(RG int k = 0; k < 4; k++){int tx = x + dx[k], ty = y + dy[k];if(tx < 1 || tx > n || ty < 1 || ty > m) continue;if(g[tx][ty] != '.' || d[tx][ty] != -1) continue;d[tx][ty] = d[x][y] + 1;qx.push(tx), qy.push(ty);}} }bool check(int t) {int d = dX.size(), p = pX.size(); DINIC::e_num = -1;clear(DINIC::head, -1); static int idcnt, id_door[N * N][N], id_p[N];DINIC::S = idcnt = 1;for(RG int i = 1; i <= t; i++)for(RG int j = 1; j <= d; j++)id_door[i][j] = ++idcnt;for(RG int i = 1; i <= t; i++)for(RG int j = 1; j <= d; j++)DINIC::add_edge(DINIC::S, id_door[i][j], 1);for(RG int i = 1; i <= p; i++)id_p[i] = ++idcnt;DINIC::T = ++idcnt;for(RG int i = 1; i <= p; i++)DINIC::add_edge(id_p[i], DINIC::T, 1);for(RG int i = 0; i < d; i++)for(RG int j = 0; j < p; j++){int ds = dis[dX[i]][dY[i]][pX[j]][pY[j]];if(ds < 0) continue;for(RG int k = ds; k <= t; k++)DINIC::add_edge(id_door[k][i + 1], id_p[j + 1], 1);}return DINIC::main() == p; }void Solve() {int lim = n * m; clear(dis, -1);for(RG int x = 1; x <= n; x++)for(RG int y = 1; y <= m; y++)if(g[x][y] == 'D') dX.push_back(x),dY.push_back(y), BFS(x, y, dis[x][y]);else if(g[x][y] == '.') pX.push_back(x), pY.push_back(y);int L = -1, R = lim + 1, ans = R;while(L <= R){int mid = (L + R) >> 1;if(check(mid)) R = mid - 1, ans = mid;else L = mid + 1;}if(ans > lim) puts("impossible");else printf("%d\n", ans); }int main() {n = read(), m = read();for(RG int i = 1; i <= n; i++)scanf("%s", g[i] + 1);Solve();return 0; }

轉載于:https://www.cnblogs.com/cj-xxz/p/10269383.html

總結

以上是生活随笔為你收集整理的【HNOI2007】紧急疏散的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。