https://codeforces.com/contest/1624/problem/G
시간 2초, 메모리 256MB
input :
- t (1 ≤ t ≤ 104)
- empty line
- n m (3 ≤ n ≤ 2 * 105, n − 1 ≤ m ≤ 2 * 105)
- vi ui wi (1 ≤ vi, ui ≤ n, 1 ≤ wi ≤ 109, vi ≠ ui)
output :
- Print t lines, each of which contains the answer to the corresponding set of input data — the minimum possible spanning tree ority.
spanning 트리를 만들 때 총 엣지의 길이의 합이 최소가 되도록 하여 출력하시오.
조건 :
-
ority of a spanning tree as the bitwise OR of all its weights
가중치들에 모두 OR 연산을 수행하여 얻은 값을 ority라고 함. -
A spanning tree is a connected subgraph of a given graph that does not contain cycles.
spanning tree라 함은 모두 연결된 부분 그래프 중 사이클을 포함하지 않은 것을 의미한다. -
n−1 edges so that the graph remains connected
n - 1개의 간선을 연결하고 -
bitwise OR weights of the edges are as small as possible
가중치들에 OR연산을 수행한 값이 가장 작도록 한다.
가장 큰 문제는 OR연산을 해서 최솟값을 만드는 것을 어떻게 할 것인가? 이다.
공부한 풀이 : source by r57shell
다음 풀이
- 스패닝 트리
- OR 연산시의 최솟값
1.에 의해서 find - union과 같은 방식을 사용할 수 있다.
비트 연산의 최솟값을 구하려면?? 이럴 때는 역으로도 생각해봐야 한다.
OR연산의 최댓값이 10억이기 때문에 비트로 나타내면 2^30 - 1을 하게 되면 모두 111..1 의 형태를 가지게 할 수 있다.
"특정"가중치를 지정한 후 해당하는 간선이 아닌 다른 것만으로도 가능하다면 누적시키는 방식을 사용한다.
그러니까 111...1 에서 불필요한 놈들을 기록한 임의의 mask [??01..?1]을 빼서 값을 얻자.
언제나 2가지 방법이 있다. 모든 경우를 확인, 또는 해당 가중치를 가진 간선을 제외하고도 spanning tree를 구성할 수 있는지 확인하는 것이다.
여기서 "특정"가중치(비트)라 함은 최대로 얻을 수 있는 값이 10억으로 2^29의 위치에서 부터 시작을 한다.
물론 현재 예제에서 확인을 해보면
해당하는 값이 1, 2, 2가 존재한다.
-> 현재 8의 값을 가지는 것을 확인
8 4 2 1
1 0 0 0
이를 통해 8의 위치에 비트가 존재하는지를 확인할 수 있다.
8을 막는다 해도 다른 놈들로 트리를 만들 수 있어 누적된 mask는 [1 0 0 0]이 된다.
-> 현재 4의 값을 가지는 것을 확인
8 4 2 1
1 1 0 0
이를 통해 4의 위치에 비트가 존재하는지를 확인할 수 있다.
4를 막는다 해도 다른 놈들로 트리를 만들 수 있어 누적된 mask는 [1 1 0 0]이 된다.
-> 현재 2의 값을 가지는 것을 확인
8 4 2 1
1 1 1 0
이를 통해 2의 위치에 비트가 존재하는지를 확인할 수 있다.
2를 막으면 트리를 만들 수 없다. 누적을 하지 않는다.
-> 현재 1의 값을 가지는 것을 확인
8 4 2 1
1 1 0 1
이를 통해 1의 위치에 비트가 존재하는지를 확인할 수 있다.
1을 막는다 해도 다른 놈들로 트리를 만들 수 있어 누적된 mask는 [1 1 0 1]이 된다.
그래서 [111...1] - [111.. 1101] => 2를 얻을 수 있다.
방식
특정 비트를 포함하는 지를 확인하기 위해 현재 w에다가 비트 연산을 한다.
비트 연산을 통해 얘를 제외하는 것이다.
특정 가중치를 계속 추가하면서 하는 방식은 너무 경우가 많다.
전체 값 - [필요없는 비트]의 경우에는 m * 29가 된다.
가중치의 최댓값이 10억이기 때문에 비트로 나타내면 개수가 29개다. 그래서 특정 비트를 막는 경우가 29번 그 때 엣지가 m개 여서 위와 같은 계산을 한다.
시간
예전에 알고리즘 과목 들으면서 들었던 건데 이 코드를 먼저 작성하신 분의 코드에서 다시 확인을 하였다.
main() 함수를 만들어서 실행을 시키면 더 빠른 실행속도를 가진다고 한다.
if __name()__ == "__name__":
main()과 같은 코드로 실행을 해서 시간적으로 이득을 보자.
import sys
def solve():
def find(node):
if parent[node] == node:
return parent[node]
parent[node] = find(parent[node])
return parent[node]
def union(a, b):
parent_a = find(a)
parent_b = find(b)
if parent_a < parent_b:
parent[parent_b] = parent_a
else:
parent[parent_a] = parent_b
sys.stdin.readline()
n, m = map(int, sys.stdin.readline().split())
e = []
for _ in range(m):
u, v, w = map(int, sys.stdin.readline().split())
e.append((u, v, w))
mask = 0
for j in range(29, -1, -1):
mm = mask | (1 << j)
parent = [i for i in range(n + 1)]
cnt = 0
for u, v, w in e:
if w & mm == 0 and find(u) != find(v):
union(u, v)
cnt += 1
if cnt == n - 1:
mask = mm
print(((1 << 30) - 1) - mask)
def main():
for i in range(int(sys.stdin.readline())):
solve()
if __name__ == '__main__':
main()OR연산은 덧셈연산과 다르다. OR연산을 한다면 비트의 개수가 고정되어 있는다는 것을 알고 있자.
