G. MinOr Tree | Round #764 Div.3

LONGNEW·2022년 1월 12일
0

CP

목록 보기
103/155

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

다음 풀이

  1. 스패닝 트리
  2. 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연산을 한다면 비트의 개수가 고정되어 있는다는 것을 알고 있자.

0개의 댓글