最大生成树+lca

徐州赛区的题目

题目

link

题意

拆掉一些边，这些边的权重最小，使得任意两点间的最短路径唯一

题解

因为路径唯一，我们想到了树形结构，然后求最大生成树，这些边都保留了下来。
因为查询的次数较多，必须用lca进行预处理

ac code

lca在线 1200ms
并查集写错了导致时间复杂度爆炸

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
140
141
142
143
144
145
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 250000+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int n, m;
struct Node{
    int u, v, w;
}edge[maxn<<1];
int tot;
int fa[maxn];
int get(int x) {
    return x==fa[x]?x:fa[x]=get(fa[x]);
}
struct Node1{
    int v, next;
}node[maxn<<1];
int cnt, head[maxn];
void add_edge(int u, int v) {
    node[cnt].v=v,node[cnt].next=head[u],head[u]=cnt++;
}
bool cmp(Node a, Node b){
    return a.w>b.w;
}
void kruskal(){
    for(int i=0; i<=n*m; i++) fa[i]=i;
    cnt=0, memset(head, -1, sizeof(head));
    sort(edge, edge+tot, cmp);
    int bian = 0;
    for(int i=0; i<tot; i++){
        Node temp=edge[i];
        int u=temp.u, v=temp.v;
        int fau = get(u), fav=get(v);
        if(fau == fav) continue;
        fa[fau] = fav;
        add_edge(u ,v), add_edge(v, u);
        bian++;
        if(bian == n*m-1) break;
    }
}
int d[maxn];
bool vis[maxn];
int f[maxn][20];
void bfs(int root){
	queue<int>que;
	d[root] = 0;
	f[root][0] = root;
	que.push(root);
	while(!que.empty()){
		int tmp = que.front();
		que.pop();
		for(int i = 1;i < 20;i++)
			f[tmp][i] = f[f[tmp][i-1]][i-1];
		for(int i = head[tmp]; i != -1;i = node[i].next){
			int v = node[i].v;
			if(v == f[tmp][0])continue;
			d[v] = d[tmp] + 1;
			f[v][0] = tmp;
			que.push(v);
		}
	}
}
int lca(int u,int v){
	if(d[u] > d[v])swap(u,v);
	int hu = d[u], hv = d[v];
	int tu = u, tv = v;
	for(int det = hv-hu, i = 0; det ;det>>=1, i++)
		if(det&1)
			tv = f[tv][i];
	if(tu == tv)return tu;
	for(int i = 20-1; i >= 0; i--){
		if(f[tu][i] == f[tv][i])
			continue;
		tu = f[tu][i];
		tv = f[tv][i];
	}
	return f[tu][0];
}
void solve(){
    int q;
    int x1, y1, x2, y2;
    cin>>q;
    kruskal();
    bfs(1);
    int s, t;
    for(int i=1; i<=q; i++){
        cin>>x1>>y1>>x2>>y2;
        s=m*(x1-1)+y1, t=m*(x2-1)+y2;
        int fa=lca(s, t);
        int ans = d[s]+d[t]-2*d[fa];
        cout<<ans<<"\n";
    }
}
int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.in", "r", stdin);
    cin>>n>>m;
    char c1, c2;
    int w1, w2;
    tot=0;
    for(int i=1; i<=n*m; i++){
        cin>>c1>>w1>>c2>>w2;
        if(c1 != 'X') edge[tot].u=i, edge[tot].v=i+m, edge[tot++].w=w1;
        if(c2 != 'X') edge[tot].u=i, edge[tot].v=i+1, edge[tot++].w=w2;
    }
    solve();
    return 0;
}

ac code

lca离线版，566ms
离线版的代码量较大，因此平时就用在线版的就行了23333

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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
#include<bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid (l+r>>1)
#define pb(x) push_back(x)
#define cls(x, val) memset(x, val, sizeof(x))
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define lowbit(x) (x&(-x))
#define inc(i, l, r) for(int i=l; i<=r; i++)
#define dec(i, r, l) for(int i=r; i>=l; i--)
const int inf = 0x3f3f3f3f;
const int maxn = 250000+10;
const double pi = acos(-1.0);
const double eps = 1e-7;
const int mod = 1e9+7;
int n, m;
struct Node{
    int u, v, w;
}edge[maxn<<1];
int tot;
int fa[maxn];
int get(int x) {
    return x==fa[x]?x:fa[x]=get(fa[x]);
}
bool vis[maxn];
int ancester[maxn];
struct Node1{
    int v, next;
}node[maxn<<1];
int cnt, head[maxn];
struct Query{
    int to, next;
    int index;
}q[100000*2];
int tt, h[maxn];
int answer[maxn];
void add_query(int u, int v, int index){
    q[tt].to = v;
    q[tt].next = h[u];
    q[tt].index = index;
    h[u] = tt++;
    q[tt].to = u;
    q[tt].next = h[v];
    q[tt].index = index;
    h[v] = tt++;
}
void uni(int u, int v){
    int fau=get(u), fav=get(v);
    if(fau!=fav) fa[fau] = fav;
}
void LCA(int u){
    vis[u] = true;
    ancester[u] = u;
    for(int i=head[u]; ~i; i=node[i].next){
        int v = node[i].v;
        if(vis[v]) continue;
        LCA(v);
        uni(u, v);
        //可能将儿子节点当成自己的fa[u], 这样就可以更新真正的父亲节点了；
        //还有一种情况就是根就是父亲节点，这样ancester更新完依旧是自己
        ancester[get(u)] = u;
    }
    for(int i=h[u]; ~i; i = q[i].next){
        int v = q[i].to;
        if(vis[v]){
            answer[q[i].index] = ancester[get(v)];
        }
    }
}
void add_edge(int u, int v) {
    node[cnt].v=v,node[cnt].next=head[u],head[u]=cnt++;
}
bool cmp(Node a, Node b){
    return a.w>b.w;
}
void kruskal(){
    for(int i=0; i<=n*m; i++) fa[i]=i;
    cnt=0, memset(head, -1, sizeof(head));
    sort(edge, edge+tot, cmp);
    int bian = 0;
    for(int i=0; i<tot; i++){
        Node temp=edge[i];
        int u=temp.u, v=temp.v;
        int fau = get(u), fav=get(v);
        if(fau == fav) continue;
        fa[fau] = fav;
        add_edge(u ,v), add_edge(v, u);
        bian++;
        if(bian == n*m-1) break;
    }
}
int d[maxn];
void bfs(int root){
	queue<int>que;
	cls(vis, 0);
	d[root] = 0;
	que.push(root);
	while(!que.empty()){
		int tmp = que.front();
		que.pop();
		if(vis[tmp]) continue;
		vis[tmp]  = true;
		for(int i = head[tmp]; i != -1;i = node[i].next){
			int v = node[i].v;
			if(vis[v])continue;
			d[v] = d[tmp] + 1;
			que.push(v);
		}
	}
}
int lx[maxn], ly[maxn];
void solve(){
    int q;
    int x1, y1, x2, y2;
    cin>>q;
    kruskal();
    bfs(1);
    int s, t;
    cls(h, -1);
    for(int i=1; i<=q; i++){
        cin>>x1>>y1>>x2>>y2;
        s=m*(x1-1)+y1, t=m*(x2-1)+y2;
        lx[i] = s, ly[i] = t;
        add_query(s, t, i);
    }
    cls(vis, 0);
    for(int i=0; i<=n*m; i++) fa[i]  =i;
    //for(int i=0; i<n*m+1; i++) get(i);
    LCA(1);
    for(int i=1; i<=q; i++){
        int ans = d[lx[i]]+d[ly[i]]-2*d[answer[i]];
        cout<<ans<<"\n";
    }
}
int main()
{
    ios::sync_with_stdio(false);
    //freopen("in.in", "r", stdin);
    cin>>n>>m;
    char c1, c2;
    int w1, w2;
    tot=0;
    for(int i=1; i<=n*m; i++){
        cin>>c1>>w1>>c2>>w2;
        if(c1 != 'X') edge[tot].u=i, edge[tot].v=i+m, edge[tot++].w=w1;
        if(c2 != 'X') edge[tot].u=i, edge[tot].v=i+1, edge[tot++].w=w2;
    }
    solve();
    return 0;
}

未解决的问题

本文标题:最大生成树+lca

文章作者:Babydragon

发布时间:2018-09-09, 23:05:55

最后更新:2018-09-09, 23:13:00

原始链接:http://baolintian.github.io/2018/09/09/最大生成树—-lca/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 题目
    1. 1.1. 题意
    2. 1.2. 题解
    3. 1.3. ac code
    4. 1.4. ac code
  2. 2. 未解决的问题
{{ live2d() }}