poj 3057

本文主要是介绍poj 3057，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

       这道题是一道用二分图最大匹配算法解决的问题，关键在于如何构图，是一道难题。

       题目里说一个门每秒只能通过一个人，这一限制条件给解题造成很大的难度。解决这道题时，要把门和时间结合起来考虑，也就是说要区分1s时刻的门和2s时刻的门，即一个人在时间为1的情况下通过门和时间为2的情况下通过同一扇门是不同的匹配。

        简单来说，构图就是把人作为X集合中的点，把门和时间一起考虑，作为Y集合中的点，如果任何情况下人不能全被匹配，说明有一些人无法逃脱，否则肯定有一个最短时间能让所有人逃脱。而为了找到最短的时间，所以从时间1s开始，构出一个二分图，求最大匹配，如果能匹配所有的点，那么这就是最短的时间，否则时间自增1s，重新构图，再求最大匹配，再判断。如果超过时间上界，我的代码里取时间上界为n*m（n为行数，m为列数），那么则无法让所有人都逃脱。由于最大匹配算法可以从一个初始匹配开始运行，所以当我们在求时间为 t s二分图的最大匹配时，可以把 t-1 s时求得的最大匹配作为一个初始匹配。

       顺便提一下，这道题算法复杂度比较高，从题目给出的范围也可以感觉到，所以要尽可能节约时间，而不能图方便做多余的操作。从我写这道题的过程来看，开始写出来TLE，后来把MAX范围从25改到15，就AC了，时间是297ms，然后再少开一些空间，用以减少memeset函数赋值的时间，AC时间降到94ms，然后减少一个memeset函数的使用，时间又降到79ms，这足以说明一些小细节对于减少这道题通过时间甚至是否AC的重要性，这也是第一次见到MAX范围大了也TLE的情况，以后要多加注意。当然，由于没有多次提交实验，肯定有误差，请不要计较细节。

       这题在《挑战程序设计竞赛》（ 人民邮电出版社） P230也有详细解题过程，而我也是参考这个写这道题的，书中对于多维数组作为参数传递的方式上值得学习，虽然不能提高效率，但很简洁，下面的代码也有体现。

代码（C++）：

#include <cstdlib>
#include <iostream>
#include <queue>
#include <vector>#define MAX 15
#define INF (1<<30)
using namespace std;//#define LOCALtypedef pair<int,int> pii;
pii p[MAX*MAX],d[MAX*MAX];vector<int> G[MAX*MAX];const int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int dist[MAX][MAX][MAX][MAX],cx[MAX*MAX],cy[2*MAX*MAX*MAX];
int n,m,cp,cd,ans;
bool vis[2*MAX*MAX*MAX];
char map[MAX][MAX];void bfs(int x,int y,int dist[MAX][MAX])
{int a,b,i;queue<pii> qi;pii tmp;dist[x][y]=0;qi.push(make_pair(x,y));while(!qi.empty()){tmp=qi.front();qi.pop();     for(i=0;i<4;i++){a=dir[i][0]+tmp.first;b=dir[i][1]+tmp.second; if(a>=0&&a<n&&b>=0&&b<m&&map[a][b]=='.'&&dist[a][b]==-1) {dist[a][b]=dist[tmp.first][tmp.second]+1;qi.push(make_pair(a,b));                   }          }        }      
}void add_edge(int a,int b)
{G[a].push_back(b);
}bool dfs(int u)
{int i,v;for(i=0;i<G[u].size();i++){v=G[u][i];if(!vis[v]){vis[v]=true;if(cy[v]==-1||dfs(cy[v])){cx[u]=v;cy[v]=u;return true;                     }       }                      }return false;
}void Hungary(int k)
{int i,j;for(i=0;i<cp;i++){if(cx[i]==-1){//memset(vis,false,sizeof(vis));for(j=0;j<cd*k;j++) vis[j]=false;if(dfs(i)) ans++;         }             } 
}int main(int argc, char *argv[])
{
#ifdef LOCALfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);
#endifint t,i,j,k;scanf("%d",&t);while(t--){scanf("%d %d",&n,&m);   for(i=0;i<n;i++) scanf("%s",map[i]); cp=cd=0;memset(dist,-1,sizeof(dist));for(i=0;i<n;i++){for(j=0;j<m;j++){if(map[i][j]=='.') p[cp++]=make_pair(i,j);else if(map[i][j]=='D'){  d[cd++]=make_pair(i,j);bfs(i,j,dist[i][j]);                                }            }            } if(cp==0){printf("0\n");continue;     }ans=0;memset(cx,-1,sizeof(cx));memset(cy,-1,sizeof(cy));for(k=1;k<n*m;k++){for(i=0;i<cp;i++){for(j=0;j<cd;j++){if(dist[d[j].first][d[j].second][p[i].first][p[i].second]!=-1&&dist[d[j].first][d[j].second][p[i].first][p[i].second]<=k) add_edge(i,j+cd*(k-1));         }             }Hungary(k);if(ans==cp){printf("%d\n",k);  break;} } if(k==n*m) printf("impossible\n");       for(i=0;i<cp;i++) G[i].clear(); }system("PAUSE");return EXIT_SUCCESS;
}

Description

Input

Output

Sample Input

3
5 5
XXDXX
X...X
D...X
X...D
XXXXX
5 12
XXXXXXXXXXXX
X..........D
X.XXXXXXXXXX
X..........X
XXXXXXXXXXXX
5 5
XDXXX
X.X.D
XX.XX
D.X.X
XXXDX

Sample Output

3
21
impossible

这篇关于poj 3057的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！