poj 3057（bfs+二分匹配）

题目链接：http://poj.org/problem?id=3057

题目大概意思是有一块区域组成的房间，房间的边缘有门和墙壁，‘X’代表墙壁，‘D’代表门，房间内部的‘ . ’代表空区域，每个空区域站一个人，人可以向上下左右走，每走一步花费一秒钟，现在房间起火了，所有人向四周的门逃生，但是每秒钟一扇门只能通过一个人，每个人移动到门时，就算逃脱，问在选取使得所有人最优的逃生方案时，最后一个逃生的人花费多长时间？如果有人无法逃生，输出impossible.

题目建图思路比较难想。考虑到任意 t 时刻，每个门只能有一个人逃生，那么第Ni个人可以在 Ti 时间从 Di号门逃生，这样就构成了一个二元组，两个集合分别为N个人和（Ti时间时，Di号门逃生），计算出N个人组合的点集和（Ti，Di）组成的二分图的匹配数，就可以判断所有人是否可以逃生，匹配数 = N时则可以逃生。在跑匈牙利算法时，当匹配数 = N，就是最后一个人逃生，其花费的时间即为答案。依次遍历区域，map[x][y] == 'D' 时候，利用一下bfs递推出各个点上的人到这扇门Di的最小距离，但是建这个点上的人到这扇门的边集时，是要从其最短距离到最大距离建边，因为每个人不一定是要走最短的路去这个门或是其他门逃生（每扇门每秒钟只能通过一人）。其中要开一个四维数组dist[x][y][k][w]（x,y表示门坐标，k，w表示人坐标）存储在点[k][w]的人到点[x][y]门的最小距离。

AC代码：

#include<iostream>

#include<algorithm>

#include<queue>

#include<cstring>

#include<vector>

using namespace std;

const int dx[4] = {-1,0,0,1},dy[4] = {0,-1,1,0};

vector<string> map;

vector<int> Di,Dj;//门的坐标

vector<int> Pi,Pj;//人的坐标

int X,Y;

int dist[15][15][15][15]; //dist[i][j][k][w]表示位于坐标(k,w)的人 到 (i,j)门的最短距离

int visit[150];//访问数组

bool g[7000][150];//建立二分图

int match[150];//每个人的匹配数组

void bfs(int a,int b){//计算最短距离

	queue<int> qx,qy;

	int n = a,m = b;

	dist[a][b][a][b] = 0;

	qx.push(a);

	qy.push(b);

	while(!qx.empty()){

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

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

		for(int  i = 0;i<4;i++){

			int tx = a + dx[i],ty = b + dy[i];

			if(tx>=0 && ty>=0 && tx<Y && ty<X && map[tx][ty] == '.' && dist[n][m][tx][ty]<0){

				dist[n][m][tx][ty] = dist[n][m][a][b] + 1;//bfs逐步计算距离

				qx.push(tx);

				qy.push(ty);

			}

		}

	}

}

bool dfs(int u){

	for(int i = 0;i<150;i++){

		if(g[u][i] && !visit[i]){

			visit[i] = true;

			if(match[i] == -1 || dfs( match[i] )){

				match[i] = u;

				return true;

			}

		}

	}

	return false;

}

void hungary(){//匈牙利算法跑二分匹配

	int ans = 0;

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

	for(int i = 0;i<X*Y*Di.size();i++){

		memset(visit,0,sizeof(visit));

		if(dfs(i))

		{

			ans++;

			if(ans == Pi.size() ){

				cout<<i/Di.size() + 1<<endl;

				return ;

			}

		}

	}

	cout<<"impossible"<<endl;

}

int main(){

	int t;

	cin>>t;

	while(t--){

		cin>>Y>>X;

		map.clear();

		Di.clear(),Dj.clear();

		Pi.clear(),Pj.clear();

		memset(dist,-1,sizeof(dist));

		memset(g,0,sizeof(g));

        //以上为初始化操作

		for(int i = 0;i<Y;i++){

			string t;

			cin>>t;

			map.push_back(t);

		}

		for(int i = 0;i<Y;i++){

			for(int j = 0;j<X;j++){

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

					Di.push_back(i),Dj.push_back(j);

					bfs(i,j);

				}

				if(map[i][j] == '.'){

					Pi.push_back(i),Pj.push_back(j);

				}

			}

		}

		for(int i = 0;i<Di.size() ;i++){

			for(int j = 0;j<Pi.size() ;j++){

				if(dist[Di[i]][Dj[i]][Pi[j]][Pj[j]] >= 0){

					for(int k = dist[Di[i]][Dj[i]][Pi[j]][Pj[j]];k<=X*Y;k++){

						g[(k-1)*Di.size() + i][j] = 1;//建边操作，点(k-1)*Di.size()+i与点j相连

						//此表示第j个人可以走 k路程到第i个门

					}

				}

			}

		}

		if(Pi.size() == 0){

			cout<<0<<endl;

		}

		hungary();

	}

	return 0;

}

巴特西

poj 3057（bfs+二分匹配）

最新文章

热门文章