| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P182SUMD - ROUND 2D - Bài toán trước bữa tiệc |
Trong một lần đặt chân lên hòn đảo X, Lù và băng của mình được ngài thị trưởng của thành phố đố 1 câu đố nếu giải được thì sẽ được chiêu đãi 1 bữa tiệc hậu hĩnh. Câu đó như sau:
Thành phố có n nút giao và có m đường đi 1 chiều giữa các nút. Để đảm bảo an ninh, ngài thị trưởng yêu cầu phải xây dựng một số trạm cảnh vệ để bảo vệ hòn đảo khỏi cướp biển. Các trạm cảnh vệ được đặt trên các nút, nhưng do các nút này được phân bố khắp hòn đảo nên chi phí xây dựng các trạm là khác nhau, 1 trạm A có thể bảo vệ nút B nếu A = B hoặc hoặc có đường đi từ A qua B sau đó trở về A.
Phải xác định số tiền tối thiếu có thể cần để đảm bảo an ninh cho tất cả các nút và số cách xây dựng.
Sau 1 chuyến hành trình dài, bộ não cao su của Lù đã không còn sức nên các bạn hay giúp Lù nhà ta nhé.
Input
Dòng đầu tiên chứa các số nguyên n số nút giao (1 ≤ n ≤ 105). Dòng tiếp theo chứa n số nguyên phân cách nhau bởi dấu cách. Số nguyên thứ i là chi phí xây trạm cảnh vệ thứ i (chi phí không âm và không vượt quá 109).
Dòng tiếp theo chứ một số nguyên m (0 ≤ m ≤ 3.105). Và m dòng tiếp theo mỗi dòng chứa hai số nguyên ui và vi (1 ≤ ui, vi ≤ n; u ≠ v). Có nghĩa là có đường đi 1 chiều từ u đến v và input đảm bảo không có nhiều hơn 1 con đường giữa 2 nút trong cùng một hướng.
Output
In ra hai số nguyên cách nhau bởi dấu cách. Số đầu tiên là số tiền tối thiểu, số thứ hai là số cách mà bạn đảm bảo an toàn modulo 1000000007 (109 + 7).
Example
Input: 3 1 2 3 3 1 2 2 3 3 2 Output: 3 1
Input: 5 2 8 0 6 0 6 1 4 1 3 2 4 3 4 4 5 5 1 Output: 8 2
| Được gửi lên bởi: | adm |
| Ngày: | 2018-07-13 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
