Các Chuyến Thăm

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ con bò ( $2 \leq N \leq 10^{5}$ ), mỗi con sở hữu một trang trại. Bò $i$ muốn đến thăm bò $a_{i}$ ( $a_{i} \neq i$ ). Cho một hoán vị $p$ của $1$ đến $N$ , các chuyến thăm diễn ra tuần tự:

Với mỗi $i$ từ $1$ đến $N$ :

Nếu bò $a_{p_{i}}$ đã rời đi, bò $p_{i}$ ở nhà
Ngược lại, bò $p_{i}$ rời đi thăm trang trại của bò $a_{p_{i}}$ , tạo ra $v_{p_{i}}$ tiếng kêu

Tìm hoán vị $p$ sao cho tổng số tiếng kêu là lớn nhất.

Dữ liệu vào

Dòng 1: Số nguyên $N$
$N$ dòng tiếp theo: Hai số nguyên $a_{i}$ và $v_{i}$ ( $0 \leq v_{i} \leq 10^{9}$ )

Dữ liệu ra

Một số nguyên duy nhất — tổng số tiếng kêu tối đa.

Ràng buộc

$2 \leq N \leq 10^{5}$
$a_{i} \neq i$
Test 2-3: $a_{i} \neq a_{j}$ với mọi $i \neq j$
Test 4-7: $N \leq 10^{3}$
Test 8-11: Không có ràng buộc thêm

Ví dụ

Input	Output	Giải thích
4 2 10 3 20 4 30 1 40	90	Với hoán vị $p = (2, 3, 4, 1)$ : bò 2 thăm bò 3 (20), bò 3 thăm bò 4 (30), bò 4 thăm bò 1 (40), bò 1 ở nhà. Tổng: 90.

Bình luận

Không có bình luận tại thời điểm này.