Codeforces 1108F MST Unification MST + LCA

发表于 分类于 阅读次数： 本文字数： 6.9k 阅读时长 ≈ 6 分钟

Description:

You are given an undirected weighted connected graph with \(n\) vertices and \(m\) edges without loops and multiple edges. The \(i\)-th edge is \(e_i = (u_i, v_i, w_i)\); the distance between vertices \(u_i\) and \(v_i\) along the edge \(e_i\) is \(w_i\) (\(1 \le w_i\)). The graph is connected, i. e. for any pair of vertices, there is at least one path between them consisting only of edges of the given graph. A minimum spanning tree (MST) in case of positive weights is a subset of the edges of a connected weighted undirected graph that connects all the vertices together and has minimum total cost among all such subsets (total cost is the sum of costs of chosen edges). You can modify the given graph. The only operation you can perform is the following: increase the weight of some edge by \(1\). You can increase the weight of each edge multiple (possibly, zero) times. Suppose that the initial MST cost is \(k\). Your problem is to increase weights of some edges with minimum possible number of operations in such a way that the cost of MST in the obtained graph remains \(k\), but MST is unique (it means that there is only one way to choose MST in the obtained graph). Your problem is to calculate the minimum number of operations required to do it. ### Input: The first line of the input contains two integers \(n\) and \(m\) (\(1 \le n \le 2 \cdot 10^5, n - 1 \le m \le 2 \cdot 10^5\)) — the number of vertices and the number of edges in the initial graph. The next \(m\) lines contain three integers each. The \(i\)-th line contains the description of the \(i\)-th edge \(e_i\). It is denoted by three integers \(u_i, v_i\) and \(w_i\) (\(1 \le u_i, v_i \le n, u_i \ne v_i, 1 \le w \le 10^9\)), where \(u_i\) and \(v_i\) are vertices connected by the \(i\)-th edge and \(w_i\) is the weight of this edge. It is guaranteed that the given graph doesn't contain loops and multiple edges (i.e. for each \(i\) from \(1\) to \(m\) \(u_i \ne v_i\) and for each unordered pair of vertices \((u, v)\) there is at most one edge connecting this pair of vertices). It is also guaranteed that the given graph is connected.

Output

Print one integer — the minimum number of operations to unify MST of the initial graph without changing the cost of MST.

Sample Input:

8 10 1 2 1 2 3 2 2 4 5 1 4 2 6 3 3 6 1 3 3 5 2 3 7 1 4 8 1 6 2 4

Sample Output:

1

Sample Input:

4 3 2 1 3 4 3 4 2 4 1

Sample Output:

0

Sample Input:

3 3 1 2 1 2 3 2 1 3 3

Sample Output:

0

Sample Input:

3 3 1 2 1 2 3 3 1 3 3

Sample Output:

1

Sample Input:

1 0

Sample Output:

0

Sample Input:

5 6 1 2 2 2 3 1 4 5 3 2 4 2 1 4 2 1 5 3

Sample Output:

2

题目链接

题解:

你有一个图，你可以增加某些边的边权使得这张图的最小生成树变成唯一的并保持最小生成树权值和不变，要求最小化边权增加量

我的做法:首先随便找一个最小生成树，然后考虑非树边\((x, y, val)\), 如果\(x到y\)的最小生成树上唯一路径的边权最大值等于\(val\),那么这条非树边的边权要增加\(1\), 因为这条边会导致非唯一的最小生成树，然后我就写了个树链剖分......总复杂度\(O(mlogm + m log^2n)\), 但是这道题没有修改，根本用不着树链剖分，只要倍增LCA的时候顺便用一个东西记录路径最大值就好了，我凭空多了一个\(log\)，跑了\(400ms\)

题解的做法:考虑跑\(kruskal\)的过程，一次考虑所有边权相同的边，去除那些连接了两个已联通点的边，剩下的边一个个加入，加入失败的边的数量贡献到答案里，复杂度\(O(mlogm)\),而且很短,很快，只要\(100ms\)

我的做法AC代码:

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
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

int head[N], pnt[N << 1], nxt[N << 1], val[N << 1], cnt;
map<int, int> vis[N];
int dep[N], dfn[N], top[N], fa[N], son[N], rnk[N], size[N], clk;
int mx[N << 2];
struct edge {
	int x, y, v;
	bool operator<(const edge &rhs) const {
		return v < rhs.v;
	}
	void adjust() {
		if(dep[x] > dep[y])
			swap(x, y);
	}
}seg[N];
int dsu[N];
int n, m, ans;

void add(int x, int y, int v) {
	pnt[cnt] = y;
	val[cnt] = v;
	nxt[cnt] = head[x];
	head[x] = cnt++;
}

int find(int x) {
	return dsu[x] == x ? x : dsu[x] = find(dsu[x]);
}

void unite(int x, int y) {
	int fx = find(x), fy = find(y);
	if(fx != fy)
		dsu[fx] = fy;
}

int kruskal() {
	int res = 0;
	sort(seg + 1, seg + m + 1);
	for(int i = 1; i <= n; ++i)
		dsu[i] = i;
	for(int i = 1; i <= m; ++i) {
		if(find(seg[i].x) == find(seg[i].y)) continue;
		vis[seg[i].x][seg[i].y] = 1;
		vis[seg[i].y][seg[i].x] = 1;
		unite(seg[i].x, seg[i].y);
		res += seg[i].v;
	}
	return res;
}

void dfs1(int rt, int pre, int depth) {
	dep[rt] = depth;
	son[rt] = -1;
	size[rt] = 1;
	fa[rt] = pre;
	for(int i = head[rt]; ~i; i = nxt[i]) {
		int j = pnt[i];
		if(j == pre) continue;
		if(!vis[rt].count(j)) continue;
		dfs1(j, rt, depth + 1);
		size[rt] += size[j];
		if(son[rt] == -1 || size[j] > size[son[rt]])
			son[rt] = j;
	}
}

void dfs2(int rt, int t) {
	top[rt] = t;
	dfn[rt] = clk;
	rnk[clk] = rt;
	clk++;
	if(son[rt] == -1)
		return;
	dfs2(son[rt], t);
	for(int i = head[rt]; ~i; i = nxt[i]) {
		int j = pnt[i];
		if(j == fa[rt] || j == son[rt]) continue;
		if(!vis[rt].count(j)) continue;
		dfs2(j, j);
	}
}

void pushup(int rt) {
	mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
}

void build(int rt, int l, int r) {
	mx[rt] = 0;
	if(l == r)
		return;
	int mid = l + r >> 1;
	build(rt << 1, l, mid);
	build(rt << 1 | 1, mid + 1, r);
}

void update(int rt, int l, int r, int pos, int val) {
	if(l == r) {
		mx[rt] = val;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid)
		update(rt << 1, l, mid, pos, val);
	else
		update(rt << 1 | 1, mid + 1, r, pos, val);
	pushup(rt);
}

int query(int rt, int l, int r, int L, int R) {
	if(L <= l && r <= R)
		return mx[rt];
	int mid = l + r >> 1, ans = 0;
	if(L <= mid)
		ans = max(ans, query(rt << 1, l, mid, L, R));
	if(mid < R)
		ans = max(ans, query(rt << 1 | 1, mid + 1, r, L, R));
	return ans;
}

int ask(int a, int b) {
	int ans = 0, ta = top[a], tb = top[b];
	while(ta != tb) {
		if(dep[ta] < dep[tb])
			swap(ta, tb), swap(a, b);
		ans = max(ans, query(1, 1, n, dfn[ta], dfn[a]));
		a = fa[ta];
		ta = top[a];
	}
	if(a == b) return ans;
	if(dep[a] > dep[b]) swap(a, b);
	return max(ans, query(1, 1, n, dfn[son[a]], dfn[b]));
}

void input() {
	memset(head, -1, sizeof(head));
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= m; ++i) {
		scanf("%d%d%d", &seg[i].x, &seg[i].y, &seg[i].v);
		add(seg[i].x, seg[i].y, seg[i].v);
		add(seg[i].y, seg[i].x, seg[i].v);
	}
}

void init() {
	clk = 1;
	kruskal();
	dfs1(1, 1, 0);
	dfs2(1, 1);
	build(1, 1, n);
	for(int i = 1; i <= m; ++i) {
		if(!vis[seg[i].x].count(seg[i].y)) continue;
		seg[i].adjust();
		update(1, 1, n, dfn[seg[i].y], seg[i].v);
	}
}

int solve() {
	for(int i = 1; i <= m; ++i) {
		if(vis[seg[i].x].count(seg[i].y)) continue;
		ans += seg[i].v == ask(seg[i].x, seg[i].y);
	}
	return ans;
}

int main() {
	input();
	init();
	printf("%d\n", solve());
	return 0;
}

题解做法AC代码:

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
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;

struct e {
	int x, y, v;
	bool operator<(const e &rhs) const {
		return v < rhs.v;
	}
}edges[N];

int dsu[N], n, m, ans, cnt;

int find(int x) {
	return x == dsu[x] ? x : dsu[x] = find(dsu[x]);
}

bool unite(int x, int y) {
	int fx = find(x), fy = find(y);
	if(fx == fy)
		return false;
	dsu[fx] = fy;
	return true;
}

int main() {
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++i)
		dsu[i] = i;
	for(int i = 1; i <= m; ++i) 
		scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].v);
	sort(edges + 1, edges + m + 1);
	int j = 1;
	for(int i = 1; i <= m; ++i) {
		j = i + 1;
		while(j <= m && edges[j].v == edges[i].v) 
			++j;
		cnt = j - i;
		for(int k = i; k < j; ++k) 
			if(find(edges[k].x) == find(edges[k].y))
				--cnt;
		for(int k = i; k < j; ++k)
			cnt -= unite(edges[k].x, edges[k].y);
		ans += cnt;
		i = j - 1;
	}
	printf("%d\n", ans);
	return 0;
}