（好题）POJ3057

二分+二分图匹配+BFS

题意：

墙壁“X”，空区域（都是人）“.”，门“D”。

人向门移动通过时视为逃脱，门每秒能出去一个人，人可以上下左右移动，墙阻止移动。

求最优移动方案下，最后一个人逃脱的最短时间。如果有人无法安全逃脱（比如被墙围困住），则输出“impossible”。

解法1：

以每个门为起点可以通过BFS来算出每个人逃离的最短路。

二分答案，判断所有的人能否在时间T内逃脱。

考虑某一个门，如果能在时间t从该门逃脱的人，应该是距离该门t以内的人，并且其中只有一人能够从该门逃脱。

每个时间和门的二元组，都能确定一个对应的能够从中逃脱的人的集合，而通过计算这个二元组和人组成的二分图的最大匹配数，我们就能判断所有人是否逃脱。

会T。

 const int dx[] = {, , , -};

 const int dy[] = {, , -, };

 int X, Y;

 char field[MAXN][MAXN];

 vector<int> dX, dY;

 vector<int> pX, pY;

 int dist[MAXN][MAXN][MAXN][MAXN];

 const int MAXV = ;

 int V;                //顶点数

 vector<int> G[MAXV];  //图的邻接表表示

 int match[MAXV];      //所匹配的定点

 bool used[MAXV];      // DFS中用到的访问标记

 //添加无向边，注意顶点编号从0开始

 void add_edge(int u, int v) {

     G[u].push_back(v);

     G[v].push_back(u);

 }

 //通过DFS寻找增广路

 bool dfs(int v) {

     used[v] = true;

     for (int i = ; i < G[v].size(); i++) {

         int u = G[v][i], w = match[u];

         if (w <  || !used[w] && dfs(w)) {

             match[v] = u;

             match[u] = v;

             return true;

         }

     }

     return false;

 }

 //二分图最大匹配，返回最大匹配数

 int Bipartite_Matching() {

     int res = ;

     memset(match, -, sizeof(match));

     for (int v = ; v < V; v++) {

         if (match[v] < ) {

             memset(used, , sizeof(used));

             if (dfs(v)) {

                 res++;

             }

         }

     }

     return res;

 }

 // 二分，这一点非常精妙

 bool C(int t) {

     // 0~d-1        时间1跑掉的人

     // d~2d-1       时间2跑掉的人

     // (t-1)d~td-1  时间t跑掉的人

     // td~td+p-1    人

     int d = dX.size(), p = pY.size();

     V = t * d + p;

     REP(i, , V) G[i].clear();

     REP(i, , d) REP(j, , p) {

         int o = dist[dX[i]][dY[i]][pX[j]][pY[j]];

         if (o >= ) {

             REP(k, o, t + )

             add_edge((k - ) * d + i, t * d + j);

         }

     }

     return Bipartite_Matching() == p;

 }

 void bfs(int x, int y, int d[MAXN][MAXN]) {

     queue<int> qx, qy;

     d[x][y] = ;

     qx.push(x);

     qy.push(y);

     while (!qx.empty()) {

         x = qx.front(), qx.pop();

         y = qy.front(), qy.pop();

         REP(i, , ) {

             int nx = x + dx[i];

             int ny = y + dy[i];

             if (nx >=  && nx < X && ny >=  && ny < Y &&

                 field[nx][ny] == '.' && d[nx][ny] < ) {

                 d[nx][ny] = d[x][y] + ;

                 qx.push(nx);

                 qy.push(ny);

             }

         }

     }

 }

 void solve() {

     int n = X * Y;

     //跑最短路

     REP(i, , dX.size()) bfs(dX[i], dY[i], dist[dX[i]][dY[i]]);

     //最短路

     int lb = -, ub = n + ;

     while (ub - lb > ) {

         int mid = (ub + lb) / ;

         C(mid) ? ub = mid : lb = mid;

     }

     if (ub > n) {

         printf("impossibe\n");

     } else {

         printf("%d\n", ub);

     }

 }

 int main() {

 #ifndef ONLINE_JUDGE

     // freopen("input.txt", "r", stdin);

 #endif  // !ONLINE_JUDGE

     int T = READ();

     while (T--) {

         dX.clear(), dY.clear();

         pX.clear(), pY.clear();

         CLR(field), SET(dist);

         X = READ();

         Y = READ();

         REP(i, , X) cin >> field[i];

         REP(i, , X) REP(j, , Y) {

             if (field[i][j] == 'D') {

                 dX.push_back(i);

                 dY.push_back(j);

             } else if (field[i][j] == '.') {

                 pX.push_back(i);

                 pY.push_back(j);

             }

         }

         solve();

     }

     return ;

 }

解法2：

在上述解法下，重复的操作是每次二分都会计算一遍匹配，所以T，那么当T增加时，根据增广路的性质，我们只需要不断增加T，每次加1，就可以找出答案。

这个其实现在也不怎么看懂。

下面是不同的地方，一样的没放上来

 void solve() {

     int n = X * Y;

     //跑最短路

     REP(i, , dX.size()) bfs(dX[i], dY[i], dist[dX[i]][dY[i]]);

     // 加边

     int d = dX.size(), p = pX.size();

     V = X * Y * d + p;

     for (int v = ; v < V; ++v) G[v].clear();

     REP(i, , d) REP(j, , p) {

         int o = dist[dX[i]][dY[i]][pX[j]][pY[j]];

         if (o >= ) REP(k, o, n + ) add_edge((k - ) * d + i, n * d + j);

     }

     // 匹配

     if (p == ) {

         printf("0\n");

         return;

     }

     int num = ;  // 匹配数

     memset(match, -, sizeof(match));

     for (int v = ; v < n * d; v++) {

         // n*d是节点总数，每个门一个，把所有情况都跑一遍

         memset(used, , sizeof(used));

         if (dfs(v)) {

             if (++num == p) {

                 printf("%d\n", v / d + );

                 return;

             }

         }

     }

     printf("impossible\n");

 }

巴特西

（好题）POJ3057

最新文章

热门文章