loj 1150(spfa预处理+二分+最大匹配)

题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26864

思路：首先是spfa预处理出每个'G'到'H'的最短距离，然后就是二分最大距离，最大匹配验证即可。

PS:这道题一开始没什么思路，然后想先最简单的spfa预处理写一下吧，然后写着写着就突然豁然开朗，有思路了！然后就AC了!

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 #include<vector>
  7 using namespace std;
  8 #define MAXN 55
  9 #define inf 1<<30
 10 #define FILL(a,b) memset(a,b,sizeof(a))
 11 
 12 vector<pair<int,int> >g,h;
 13 
 14 int n,dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
 15 int dist[MAXN][MAXN],dd[MAXN][MAXN];
 16 bool mark[MAXN][MAXN];
 17 char map[MAXN][MAXN];
 18 
 19 void spfa(int vs)
 20 {
 21     FILL(mark,false);
 22     for(int i=0;i<MAXN;i++)
 23         for(int j=0;j<MAXN;j++)dd[i][j]=inf;
 24     queue<pair<int,int> >que;
 25     que.push(make_pair(g[vs].first,g[vs].second));
 26     dd[g[vs].first][g[vs].second]=0;
 27     while(!que.empty()){
 28         pair<int,int>p=que.front();
 29         que.pop();
 30         mark[p.first][p.second]=false;
 31         for(int i=0;i<4;i++){
 32             int x=p.first+dir[i][0],y=p.second+dir[i][1];
 33             if(x>=0&&x<n&&y>=0&&y<n&&map[x][y]!='#'){
 34                 if(dd[p.first][p.second]+1<dd[x][y]){
 35                     dd[x][y]=dd[p.first][p.second]+1;
 36                     if(!mark[x][y]){
 37                         mark[x][y]=true;
 38                         que.push(make_pair(x,y));
 39                     }
 40                 }
 41             }
 42         }
 43     }
 44 }
 45 
 46 vector<int>gg[MAXN];
 47 void Build(int limit)
 48 {
 49     for(int i=0;i<MAXN;i++)gg[i].clear();
 50     for(int i=0;i<g.size();i++){
 51         for(int j=0;j<h.size();j++){
 52             if(dist[i][j]<=limit)gg[i].push_back(j);
 53         }
 54     }
 55 }
 56 
 57 int ly[MAXN];
 58 bool vis[MAXN];
 59 
 60 int dfs(int u)
 61 {
 62     for(int i=0;i<gg[u].size();i++){
 63         int v=gg[u][i];
 64         if(!vis[v]){
 65             vis[v]=true;
 66             if(ly[v]==-1||dfs(ly[v])){
 67                 ly[v]=u;
 68                 return 1;
 69             }
 70         }
 71     }
 72     return 0;
 73 }
 74 
 75 int MaxMatch()
 76 {
 77     int res=0;
 78     FILL(ly,-1);
 79     for(int i=0;i<g.size();i++){
 80         FILL(vis,false);
 81         res+=dfs(i);
 82     }
 83     return res;
 84 }
 85 
 86 int main()
 87 {
 88     int _case,t=1;
 89     scanf("%d",&_case);
 90     while(_case--){
 91         scanf("%d",&n);
 92         g.clear();
 93         h.clear();
 94         for(int i=0;i<n;i++)scanf("%s",map[i]);
 95         for(int i=0;i<n;i++){
 96             for(int j=0;j<n;j++){
 97                 if(map[i][j]=='G')g.push_back(make_pair(i,j));
 98                 else if(map[i][j]=='H')h.push_back(make_pair(i,j));
 99             }
100         }
101         for(int i=0;i<MAXN;i++)
102             for(int j=0;j<MAXN;j++)dist[i][j]=inf;
103         for(int i=0;i<g.size();i++){
104             spfa(i);
105             for(int j=0;j<h.size();j++){
106                 if(dd[h[j].first][h[j].second]!=inf)dist[i][j]=min(dist[i][j],2*dd[h[j].first][h[j].second]+2);
107             }
108         }
109         int low=inf,high=0,mid,ans=inf;
110         for(int i=0;i<g.size();i++){
111             for(int j=0;j<h.size();j++){
112                 if(dist[i][j]!=inf){
113                     low=min(low,dist[i][j]);
114                     high=max(high,dist[i][j]);
115                 }
116             }
117         }
118         while(low<=high){
119             mid=(low+high)>>1;
120             Build(mid);
121             if(MaxMatch()==(int)h.size()){
122                 ans=mid;
123                 high=mid-1;
124             }else
125                 low=mid+1;
126         }
127         printf("Case %d: ",t++);
128         if(ans!=inf){
129             printf("%d
",ans);
130         }else
131             puts("Vuter Dol Kupokat");
132     }
133     return 0;
134 }

View Code