「2018 ACM-ICPC Xuzhou - Online」J - Maze Designer(最大生成树+LCA)

发表于 | 分类于 ，

J-Maze Designer
建立最大生成树，求树上任意两点之间的距离

题意

给定一个$n×m$的网格，在两个相邻点之间建立一堵墙会有一定的花费。建立一个迷宫，使任意两点之间只有一条路径可达，求在最低建造成本下，给定任意两点之间的路径。

思路

考虑在所有墙都建立的情况下，移除若干堵墙，使所有点连通，让所有点连通的最大花费即为题目所求的建造方案。建立最大生成树后求两点间的LCA，即可求解。

*我也不知道我比赛时候写的离线LCA有啥问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn=250000+10;

struct edge
{
    int u,v;
    long long cost;
    bool operator < (const edge &e) const {
        return cost>e.cost;
    }
}es[2*maxn];

int pre[maxn],cnt,E,V;
vector<int> tree[maxn];

int Find(int x) {return pre[x]==x?x:pre[x]=Find(pre[x]); }

void kruskal()
{
    for(int i=1;i<=V;i++) pre[i]=i;
    sort(es,es+E);
    for(int i=0;i<E;i++)
    {
        edge e=es[i];
        int fx=Find(e.u),fy=Find(e.v);
        if(fx!=fy)
        {
            pre[fx]=fy;
            tree[e.v].push_back(e.u);
            tree[e.u].push_back(e.v);
        }
    }
}

int dep[maxn],fa[maxn+1][30];

/**************预处理过程**************/

void dfs(int u,int pre)	//预处理各节点深度+初始fa[u][0]
{
	dep[u]=dep[pre]+1;
	fa[u][0]=pre;
	for(int i=0;i<tree[u].size();i++)
	{
		int v=tree[u][i];
		if(v!=pre) dfs(v,u);
	}
}

void init()	//预处理fa数组
{
	for(int i=1;(1<<i)<=V;i++)
		for(int u=1;u<=V;u++)
			fa[u][i]=fa[fa[u][i-1]][i-1];
}

/**************求LCA(u,v)**************/

int LCA(int u,int v)
{
	if(dep[u]<dep[v])
		swap(u,v);

	int d=dep[u]-dep[v];
	for(int i=0;(1<<i)<=d;i++)	//将u上调d个距离
		if((1<<i)&d) u=fa[u][i];

	if(u==v) return u;	//特判此时u,v是否在同一位置，如果是，u,v都在LCA上

	for(int i=(int)log(V);i>=0;i--)	//同时上调u,v
	{
		if(fa[u][i]!=fa[v][i])
		{
			u=fa[u][i];
			v=fa[v][i];
		}
	}
	return fa[u][0];	//最后会使u,v成为LCA的子节点
}

int main()
{
    int n,m,q,x1,x2,y1,y2,u,v;
    long long w1,w2;
    char s1[5],s2[5];
    scanf("%d%d",&n,&m);
    cnt=0;
    V=n*m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%s%lld%s%lld",s1,&w1,s2,&w2);
            if(s1[0]=='D')
            {
                es[cnt].u=(i-1)*n+j;
                es[cnt].v=i*n+j;
                es[cnt++].cost=w1;
            }
            else if(s1[0]=='R')
            {
                es[cnt].u=(i-1)*n+j;
                es[cnt].v=(i-1)*n+j+1;
                es[cnt++].cost=w1;
            }
            if(s2[0]=='D')
            {
                es[cnt].u=(i-1)*n+j;
                es[cnt].v=i*n+j;
                es[cnt++].cost=w2;
            }
            else if(s2[0]=='R')
            {
                es[cnt].u=(i-1)*n+j;
                es[cnt].v=(i-1)*n+j+1;
                es[cnt++].cost=w2;
            }
        }
    }
    E=cnt;
    kruskal();
    dfs(1,0);
    init();
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        u=(x1-1)*n+y1;
        v=(x2-1)*n+y2;
        int root=LCA(u,v);
        printf("%d\n",-2*dep[root]+dep[u]+dep[v]);
    }
    return 0;
}