VM 15 Bài 12 - Phân nhóm đồ thị

View as PDF

Submit solution

Points: 2.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
VM15 - khanhptnk
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Đất nước xinh đẹp ~X~ có ~N~ thành phố và có ~M~ mối quan hệ kinh tế giữa các thành phố. Mối quan hệ kinh tế này là song phương, do đó thành phố ~u~ có mối quan hệ kinh tế với thành phố ~v~ tức là thành phố ~v~ có mối quan hệ kinh tế với ~u~.

Tổng thống của nước ~X~ muốn chia đất nước của mình thành ~K~ bang nhỏ ~(N~ chia hết cho ~K)~, nhưng ông lại muốn tối thiểu hóa quan hệ kinh tế giữa các bang với nhau. Tổng số lượng quan hệ kinh tế giữa các bang là số lượng cặp ~(u~, ~v)~ với thành phố ~u~, ~v~ thuộc ~2~ bang khác nhau và có mối quan hệ kinh tế với nhau

Do đó nhiệm vụ được đặt ra là: Chia ~N~ thành phố thành ~K~ bang sao cho:

  • Mỗi bang có số lượng thành phố bằng nhau
  • Tổng số lượng quan hệ kinh tế giữa các bang là nhỏ nhất.

Input

  • Dòng ~1~: chứa ~3~ số nguyên dương ~N~, ~M~ và ~K~ ~\left(1 \leq N \leq 500, 0 \leq M \leq \frac{N \times (N - 1)}{2}\right)~.
  • ~M~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên ~u~ và ~v~ thể hiện có mối quan hệ kinh tế trực tiếp giữa ~u~ và ~v~.

Output

  • Dòng ~1~: Tổng số lượng quan hệ kinh tế giữa các bang.
  • ~K~ dòng tiếp theo, dòng thứ ~i~ gồm ~\frac{N}{K}~ số nguyên dương là các thành phố thuộc bang thứ ~i~

Giới hạn

  • Gọi Tổng số lượng kinh tế giữa các bang của lời giải ban tổ chức là ~X~
  • Gọi Tổng số lượng kinh tế giữa các bang của lời giải bạn là ~Y~
  • Gọi ~P~ là số điểm của test.
  • Điểm của bạn nhận được là ~\min \left(\frac{X+1}{Y+1} \times P \times 95\%, P \right)~

Sample Input

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

Sample Output

Output 1:

9
1 2
3 4
5 6

Output 2:

8
1 4
2 5
3 6

Note

Giả sử tổng số lượng kinh tế giữa các bang của ban tổ chức là ~9~, và điểm của test là ~1~ điểm:

  • Với Output 1: Bạn được ~0.95~ điểm
  • Với Output 2: Bạn được ~1~ điểm

Comments

Please read the guidelines before commenting.


There are no comments at the moment.