Maze Designer(2018徐州网络赛J题，最大生成树+LCA)_综合

徐州网络赛 - J

Maze Designer

After the long vacation, the maze designer master has to do his job. A tour company gives him a map which is a rectangle. The map consists of N×M little squares. That is to say, the height of the rectangle is N and the width of the rectangle is M. The master knows exactly how the maze is going to use. The tour company will put a couple in two different squares in the maze and make them seek each other. Of course,the master will not make them find each other easily. The only thing the master does is building some wall between some little squares. He knows in that way, wherever the couple is put, there is only one path between them. It is not a difficult thing for him, but he is a considerate man. He also knows that the cost of building every wall between two adjacent squares is different(Nobody knows the reason). As a result, he designs the maze to make the tour company spend the least money to build it.

Now, here’s your part. The tour company knows you’re the apprentice of the master, so they give you a task. you’re given Q qustions which contain the information of where the couple will be put. You need to figure out the length of the shortest path between them.

However,the master doesn’t tell you how he designs the maze, but he believes that you, the best student of himself, know the way. So he goes on vacation again.

Input

The first line of the input contains two integers N and M (1≤N,M≤500), giving the number of rows and columns of the maze.

The next N×M lines of the input give the information of every little square in the maze, and their coordinates are in order of (1,1) , (1,2) ? (1,M) , (2,1) , (2,2) , ? , (2,M) , ? ,(N,M).

Each line contains two characters D and R and two integers a , b(0≤a,b≤2000000000 ), a is the cost of building the wall between it and its lower adjacent square, and bb is the cost of building the wall between it and its right adjacent square. If the side is boundary, the lacking path will be replaced with X 0.

The next line contains an integer Q (1≤Q≤100000 ), which represents the number of questions.
The next Q lines gives four integers, x1, y1, x2, y2( 1≤x1,x2≤N, 1≤y1,y2≤M ), which represent two squares and their coordinate are (x1,y1) and (x2,y2).
(x,y) means row x and column y.

It is guaranteed that there is only one kind of maze.

Output

For each question, output one line with one integer which represents the length of the shortest path between two given squares.

样例输入

样例输出

4
2
2

分析

这个题目思维成分还是有点高的，题目是先给你一个N×M的格子图，我们已知的是图上任意两格之间有且只有一条路。给定每个格子和右边的格子以及下边的格子之间造墙的花费，要求花费最少，但是不告诉你是如何造墙的，所以这个墙是怎么样的是我们要解决的第一个问题。
实际上要墙花费最少，而我们的花费就是从所有墙里面扣掉每条路之间的墙之后的花费。总共墙的花费一定，我们路之间的墙的花费越大越好，而我们的路要满足任意两格之间都有且只有一条路，实际上所有的路就是一颗树，于是我们的问题就转换成了求最大生成树的问题。
有了这个树之后，后面的询问就很好解决了，询问是q个两点间距离，实际上就是树上两点距离求解，就是LCA，然后就可以解决了。

参考代码

#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
#define MAXN 250010
const int DEG=32;
typedef long long ll;
using namespace std;
int head[MAXN],tot=0,xa,ya,xb,yb;
int pre[MAXN];
bool vis[MAXN];
int N,M,Q,cnt=0;
ll a,b;
char ch1,ch2;
struct Edge {
    int to,next;ll w;
}edge[MAXN*2];
struct Edge1 {
    int u,v;ll w;
}e1[MAXN*2];
int fa[MAXN][DEG];
int deg[MAXN];
ll ans,cost[MAXN][DEG];void addedge(int u,int v,ll w) {
    edge[tot].to=v;edge[tot].w=w;edge[tot].next=head[u];head[u]=tot++;
}// 倍增求LCA模板
void BFS(int root) {
    queue<int>que;deg[root]=0;fa[root][0]=root;que.push(root);while(!que.empty()) {
    int tmp = que.front();que.pop();for (int i=1;i<DEG;i++) {
    fa[tmp][i]=fa[fa[tmp][i-1]][i-1];cost[tmp][i]=cost[fa[tmp][i-1]][i-1]+cost[tmp][i-1];}for (int i=head[tmp];i!=-1;i=edge[i].next) {
    int v=edge[i].to;if (v==fa[tmp][0]) continue;cost[v][0]=edge[i].w;deg[v]=deg[tmp]+1;fa[v][0]=tmp;que.push(v);}}
}ll LCA(int u,int v) {
    if (deg[u]>deg[v]) swap(u,v);int hu=deg[u],hv=deg[v];int tu=u,tv=v;ll ans=0;for (int det=hv-hu,i=0;det;det>>=1,i++) {
    if (det&1) {
    ans+=cost[tv][i];tv=fa[tv][i];}}if (tu==tv) return ans;for (int i = DEG-1;i>=0 && tu!=tv;i--) {
    if (fa[tu][i]==fa[tv][i])continue;ans+=cost[tu][i]+cost[tv][i];tu=fa[tu][i];tv=fa[tv][i];}ans+=cost[tu][0]+cost[tv][0];return ans;
}// 最大生成树
int find(int x) {
    if (pre[x]==x) return x;return pre[x]=find(pre[x]);
}void combine(int u,int v) {
    int x=find(u),y=find(v);if (x!=y) pre[y]=x;
}void kruskal() {
    for (int i=1;i<=cnt;i++) {
    if (find(e1[i].u)!=find(e1[i].v)) {
    combine(e1[i].u,e1[i].v);addedge(e1[i].u,e1[i].v,1);addedge(e1[i].v,e1[i].u,1);}}
}// 初始化
void init() {
    tot=0;memset(vis,false,sizeof(vis));memset(head,-1,sizeof(head));memset(cost,0,sizeof(cost));memset(deg,0,sizeof(deg));for (int i=0;i<=N*M;i++) pre[i]=i;
}bool cmp(Edge1 e1,Edge1 e2) {
    return e1.w>e2.w;
}int main() {
    scanf("%d%d",&N,&M); getchar();init();// 将二维坐标化为一维坐标for (int i=1;i<=N*M;i++) {
    scanf("%c %lld %c %lld",&ch1,&a,&ch2,&b); getchar();if (ch1=='D') {
    e1[++cnt].u=i; e1[cnt].v=i+M; e1[cnt].w=a;}if (ch2=='R') {
    e1[++cnt].u=i; e1[cnt].v=i+1; e1[cnt].w=b;}}sort(e1+1,e1+cnt+1,cmp);kruskal();// 以下为LCA部分BFS(1);scanf("%d",&Q);for (int i=1;i<=Q;i++) {
    scanf("%d%d%d%d",&xa,&ya,&xb,&yb);printf("%lld\n",LCA((xa-1)*M+ya,(xb-1)*M+yb));}return 0;
}