OJ题号：
BZOJ4242、AtCoder-JOISC2014E
题目大意：
给你一个h*w的网格图，每个格子可能是空地、障碍物和建筑物。
你只可以从空地上走过或者从建筑物中穿过。
建筑物总共有p个，现在有q组询问，求从建筑物A到建筑物B的过程中在空地上连续走过的最长一段路最短能是多少。
思路：
为了保证走过的最长路最短，我们可以对所有的建筑物及其路径构造最小生成树。
正确性显然：为了保证最长路最短，我们要使所有能走的边尽量小，这实际上就是一个贪心，也就是我们所熟知的Kruskal算法。
题目并没有告诉你总共有哪些边，而原图又是一个网格图，暴力算出所有的边显然会TLE，因此需要考虑如何将所有可能边算出来。
我们可以对原图进行BFS，首先将所有的建筑物加入到队列中，然后对每个建筑物向外扩展。
如果当两个建筑物所扩展到的范围出现重叠时，我们就将经由该格点的连接两个建筑物的路径加入边集。
如果两个建筑物最后扩展到的范围被其它建筑物的范围所阻断，不能直接相连，那么说明这两个点可以经由另一个点中转达到更优。
然而两个建筑物可能会重叠好几次，这时候并不一定要判重，因为每个格点上最多会被连4条边，整个图就最多有h*w*4条边，事实上远远达不到这个值。
实践证明用map判重反而比不判重要慢。
每次还要特判重叠的范围是不是属于同一个建筑物，不然会多加很多边，还会MLE。
然后跑一遍Kruskal求最小生成树即可。
最后的询问就相当于树上RMQ，用稀疏表或者树剖之类的数据结构维护一下即可。
然后交到AtCoder上随随便便拿了Rank1，吊打yutaka1999。
交到BZOJ上无限RE。
不放心，觉得是系统环境的问题，用Ubuntu测了一发，还是AC。
找管理员要数据被告知就是官方数据。
把C++流读入改成C标准读入就A了。
#include<queue>
#include<vector>
#include<cstdio>
#include<cctype>
#include<algorithm> inline int getint() {
register char ch;
while(!isdigit(ch=getchar()));
register int x=ch^'';
while(isdigit(ch=getchar())) x=(((x<<)+x)<<)+(ch^'');
return x;
}
inline bool isMasu(const char &ch) {
return ch=='.'||ch=='#';
}
inline char getmasu() {
register char ch;
while(!isMasu(ch=getchar()));
return ch;
} const int inf=0x7fffffff;
const int dx[]={,-,,},dy[]={,,,-};
const int H=,W=,P=,logP=,Q=; int h,w,p;
int map[H][W]={{}}; class DisjointSet {
private:
int anc[P];
int find(const int &x) {
return x==anc[x]?x:anc[x]=find(anc[x]);
}
public:
DisjointSet() {
for(register int i=;i<P;i++) {
anc[i]=i;
}
}
void Union(const int &x,const int &y) {
anc[find(x)]=find(y);
}
bool isConnected(const int &x,const int &y) {
return find(x)==find(y);
}
};
DisjointSet s; struct Edge1 {
int u,v,w;
bool operator < (const Edge1 &another) const {
return w<another.w;
}
};
std::vector<Edge1> e1; struct Edge {
int to,w;
};
std::vector<Edge> e[P];
inline void add_edge(const int &u,const int &v,const int &w) {
e[u].push_back((Edge){v,w});
} struct State {
int dis,root;
};
State vis[H][W]; struct Point {
int x,y;
bool onMap() const {
return x&&y&&x<=h&&y<=w;
}
};
std::queue<Point> q; inline void bfs() {
for(register int i=;i<=h;i++) {
for(register int j=;j<=w;j++) {
if(map[i][j]>) {
q.push((Point){i,j});
vis[i][j]=(State){,map[i][j]};
} else {
vis[i][j]=(State){-,};
}
}
}
while(!q.empty()) {
const Point a=q.front();
q.pop();
for(register int i=;i<;i++) {
Point b=(Point){a.x+dx[i],a.y+dy[i]};
if(!b.onMap()) continue;
if(!~map[b.x][b.y]) continue;
if(vis[b.x][b.y].root) {
const int &u=vis[a.x][a.y].root,&v=vis[b.x][b.y].root,w=vis[a.x][a.y].dis+vis[b.x][b.y].dis;
if(u==v) continue;
e1.push_back((Edge1){u,v,w});
} else {
vis[b.x][b.y]=(State){vis[a.x][a.y].dis+,vis[a.x][a.y].root};
q.push((Point){b.x,b.y});
}
}
}
} inline void kruskal() {
std::sort(e1.begin(),e1.end());
for(register std::vector<Edge1>::iterator i=e1.begin();i!=e1.end();i++) {
const int &u=i->u,&v=i->v,&w=i->w;
if(s.isConnected(u,v)) continue;
s.Union(u,v);
add_edge(u,v,w);
add_edge(v,u,w);
}
e1.clear();
} class SparseTable {
private:
int dep[P];
int anc[P][logP],max[P][logP];
int log2(const float &x) const {
return ((unsigned&)x>>&)-;
}
void dfs(const int &x) {
dep[x]=dep[anc[x][]]+;
for(int i=;i<=log2(dep[x]);i++) {
anc[x][i]=anc[anc[x][i-]][i-];
max[x][i]=std::max(max[x][i-],max[anc[x][i-]][i-]);
}
for(std::vector<Edge>::iterator i=e[x].begin();i!=e[x].end();i++) {
const int &y=i->to;
if(y==anc[x][]) continue;
anc[y][]=x;
max[y][]=i->w;
dfs(y);
}
e[x].clear();
}
public:
void init() {
for(register int i=;i<=p;i++) {
if(!dep[i]) {
dfs(i);
}
}
}
int query(int x,int y) const {
if(!s.isConnected(x,y)) return -;
int ret=;
while(dep[x]!=dep[y]) {
if(dep[x]<dep[y]) {
std::swap(x,y);
}
for(register int i=log2(dep[x]);i>=;i--) {
if(dep[anc[x][i]]>=dep[y]) {
ret=std::max(ret,max[x][i]);
x=anc[x][i];
}
}
}
if(x==y) return ret;
for(register int i=log2(dep[x]);i>=;i--) {
if(anc[x][i]!=anc[y][i]) {
ret=std::max(ret,std::max(max[x][i],max[y][i]));
x=anc[x][i],y=anc[y][i];
}
}
ret=std::max(ret,std::max(max[x][],max[y][]));
return ret;
}
};
SparseTable t; int main() {
h=getint(),w=getint(),p=getint();
const int q=getint();
for(register int i=;i<=h;i++) {
for(register int j=;j<=w;j++) {
if(getmasu()=='#') map[i][j]=-;
}
}
for(register int i=;i<=p;i++) {
const int x=getint(),y=getint();
map[x][y]=i;
}
bfs();
kruskal();
t.init();
for(register int i=;i<q;i++) {
printf("%d\n",t.query(getint(),getint()));
}
return ;
}
附官方题解：