POJ 3051 bfs 二部图最大匹配
2018-05-04 本文已影响0人
fruits_
题目链接戳这里
题意：有一个X*Y的区域，每块可能是墙壁‘X'或者是空的'.'，或者门'D'，每个空位有1个人，上下左右4个方向移动要1s，每个门1秒钟只能通过一个人，问所有人最快出去要多久？有人出不去就输出impossible。
方法：
第一种思路：利用二分法判断T时刻所有人能否出去，从而找最短时间。那么，如何判断T时刻所有人是否都能出去？考虑某一个人，他有许多选择：某一个t1时刻能出往d1号门，t2时刻能出往d2号门...(tmax <= T)即我们可以根据人和 (时间，门)的连边形成一个二部图，那么最大匹配即是在T时刻能出去的人数了。
于是可以写出下面这样一大串代码：
// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define sz size()
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e5 + 5;
const int maxX = 15, maxY = 15;
int N, M, T;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
// Input
int X, Y;
char field[maxX][maxY + 1];
vector<pii> door; // 门的坐标
vector<pii> peop; // 人的坐标
int dist[maxX][maxY][maxX][maxY];
vector<int> G[maxN];
int match[maxN];
bool used[maxN];
void add_edge(int x, int y) {
G[x].pb(y);
G[y].pb(x);
}
int dfs(int v) {
used[v] = 1;
rep(i, 0, G[v].sz) {
int u = G[v][i], w = match[u];
if (w < 0 || (!used[w] && dfs(w))) {
match[v] = u;
match[u] = v;
return 1;
}
}
return 0;
}
int bipratite_matching() {
int ret = 0;
mst(match, -1);
rep(i, 0, N) {
if (match[i] < 0) {
mst(used, 0);
if (dfs(i))
++ret;
}
}
return ret;
}
// 判断所有人是否能够在时间t以内安全逃离
bool ok(int t) {
int d = door.sz, p = peop.sz;
// 0~d-1 时间1对应的门
// d~2d-1 时间2对应的门
// (t-1)d~td-1 时间t对应的门
// td~td+p-1 人
N = t * d + p;
rep(v, 0, N) G[v].clear();
rep(i, 0, d) {
rep(j, 0, p) {
int dis = dist[door[i].fi][door[i].se][peop[j].fi][peop[j].se];
if (dis >= 0) {
rep(k, dis, t + 1) {
add_edge((k - 1) * d + i, t * d + j);
}
}
}
}
int ans = bipratite_matching();
return ans == p;
}
void bfs(int x, int y, int d[maxX][maxY]) {
queue<pii> Q;
d[x][y] = 0;
Q.push(pii(x, y));
while (Q.sz) {
pii cur = Q.front(); Q.pop();
rep(k, 0, 4) {
int nx = cur.fi + dx[k], ny = cur.se + dy[k];
if (0 <= nx && nx < X && 0 <= ny && ny < Y
&& field[nx][ny] == '.' && d[nx][ny] < 0) {
d[nx][ny] = d[cur.fi][cur.se] + 1;
Q.push(pii(nx, ny));
}
}
}
}
void solve() {
int n = X * Y;
door.clear(); peop.clear();
mst(dist, -1);
// 计算到各个门的最近距离
rep(x, 0, X) {
rep(y, 0, Y) {
if (field[x][y] == 'D') {
door.pb(pii(x, y));
bfs(x, y, dist[x][y]);
} else if (field[x][y] == '.') {
peop.pb(pii(x, y));
}
}
}
// 二分法
int le = -1, ri = n + 1;
while (ri - le > 1) {
int mid = (ri + le) / 2;
if (ok(mid)) ri = mid;
else le = mid;
}
if (ri == n + 1)
puts("impossible");
else {
printf("%d\n", ri);
}
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d %d\n", &X, &Y);
rep(i, 0, X)
scanf("%s", field[i]);
solve();
}
return 0;
}
但是会超时。因为每一次二分，都得重新根据判断的时间上限T来构图。其实！要啥二分啊，还要啥二分？直接拿所有的时间和门组成的元组和人都进行一个连边，形成一个二部图，然后直接进行一个最大匹配。求最大匹配过程中，若是匹配数够了人数，直接输出当前时间即可。
这里解释两个东西：
-
时间和门组成的元素=n*d，而n=X*Y。为何？其实这里相当于认为最大时间是X*Y，实际比这小一些，因为如果可以成功都出去，最大时间应该是“所有人”从一个门出去的时间，这里取大了是无妨的。
-
如果匹配数够了p人，那么为啥输出v/d+1？因为我们开始匹配的一侧是(时间，门号)元组，它的编号是“当前时间 * 总门数 + 门号"，求时间那在代码里就是v/d+1了。代码如下，最后，别忘记每个case的vector等要初始化好。
// #include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
#include <cmath>
using namespace std;
#define pii pair<int,int>
#define ll long long
#define mst(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define rrep(i,a,b) for(ll i=(b-1);i>=a;--i)
#define fi first
#define se second
#define sz size()
#define lb lower_bound
#define ub upper_bound
#define pb push_back
const double eps = 1e-8, PI = acos(-1.0f);
const int inf = 0x3f3f3f3f, maxN = 1e5 + 5;
const int maxX = 15, maxY = 15;
int N, M, T;
const int dx[] = {0, 0, -1, 1};
const int dy[] = {1, -1, 0, 0};
// Input
int X, Y;
char field[maxX][maxY + 1];
vector<pii> door; // 门的坐标
vector<pii> peop; // 人的坐标
int dist[maxX][maxY][maxX][maxY];
vector<int> G[maxN];
int match[maxN];
bool used[maxN];
void add_edge(int x, int y) {
G[x].pb(y);
G[y].pb(x);
}
int dfs(int v) {
used[v] = 1;
rep(i, 0, G[v].sz) {
int u = G[v][i], w = match[u];
if (w < 0 || (!used[w] && dfs(w))) {
match[v] = u;
match[u] = v;
return 1;
}
}
return 0;
}
void bfs(int x, int y, int d[maxX][maxY]) {
queue<pii> Q;
d[x][y] = 0;
Q.push(pii(x, y));
while (Q.sz) {
pii cur = Q.front(); Q.pop();
rep(k, 0, 4) {
int nx = cur.fi + dx[k], ny = cur.se + dy[k];
if (0 <= nx && nx < X && 0 <= ny && ny < Y
&& field[nx][ny] == '.' && d[nx][ny] < 0) {
d[nx][ny] = d[cur.fi][cur.se] + 1;
Q.push(pii(nx, ny));
}
}
}
}
void solve() {
int n = X * Y;
door.clear(); peop.clear();
mst(dist, -1);
// 计算到各个门的最近距离
rep(x, 0, X) {
rep(y, 0, Y) {
if (field[x][y] == 'D') {
door.pb(pii(x, y));
bfs(x, y, dist[x][y]);
} else if (field[x][y] == '.') {
peop.pb(pii(x, y));
}
}
}
// 建立图
int d = door.sz, p = peop.sz;
N = X * Y * d + p;
rep(v, 0, N) G[v].clear();
rep(i, 0, d) {
rep(j, 0, p) {
int dis = dist[door[i].fi][door[i].se][peop[j].fi][peop[j].se];
if (dis >= 0) {
rep(k, dis, n + 1)
add_edge((k - 1) * d + i, n * d + j);
}
}
}
if (p == 0) {
puts("0");
return;
}
int num = 0;
mst(match, -1);
rep(v, 0, n * d) {
mst(used, 0);
if (dfs(v)) {
if (++num == p) {
printf("%lld\n", v / d + 1);
return;
}
}
}
puts("impossible");
}
int main() {
// freopen("data.in", "r", stdin);
scanf("%d", &T);
while (T--) {
scanf("%d %d\n", &X, &Y);
rep(i, 0, X)
scanf("%s", field[i]);
solve();
}
return 0;
}
