Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

ACM_0236 - ДОЛОЙ ПРЕГРАДЫ

   Один фермер решил выделить каждому из своих животных отдельный участок луга, где они будут пастись. Для этого он вбил в землю несколько столбиков и протянул между ними проволоку разной толщины. Таким образом он получил несколько участков, некоторые из которых граничили между собой, причем на каждом участке паслось ровно одно животное. Отметим, что каждый участок в объединении со своей границей представляет собой замкнутую односвязную область.

   Животным такое нововведение не понравилось, ведь они привыкли пастись вместе, потому они решили разрушить ограждения так, чтобы иметь возможность собраться на любом из заданных участков. Определите, какова минимальная суммарная толщина проволоки, которую им для этого следует перегрызть.

Формат входных данных

   В первой строке одно целое положительное число N – количество областей, 1 N 90 000. Далее N блоков по 3 строки в каждом – описание областей.

   В первой строке i-го блока одно целое положительное число Ki – количество столбиков (и, соответственно, сегментов проволоки) на границе i-ой области, 3 Ki 600.

   Во второй строке i-го блока Ki различных целых неотрицательных чисел через пробел – номера столбиков, входящих в границу i-ой области в порядке обхода по часовой стрелке

   В третьей строке i-го блока Ki целых неотрицательных чисел через пробел Wi,j – толщина проволоки между соответствующими столбиками границы, 1  Wi,j 100 000. Wi,1 соответствует участку между первым и вторым столбиком, Wi,2 – между вторым и третьим, и так далее. Wi,Ki соответствует участку границы между последним и первым столбиками.

   Гарантируется, что номера столбиков не превышают 5 000 000, а их общее количество не превы- шают 600 000. Также гарантируется, что если один участок границы принадлежит двум областям, то указанная для него толщина проволоки будет одинаковой. Гарантируется, что каждый участок границы принадлежит не более чем двум подобластям.

Формат выходных данных

   В первой и единственной строке одно целое неотрицательное число – суммарная толщина про- волоки, которую необходимо перегрызть, чтобы каждое животное имело возможность пройти на любой из исходных участков.

Примеры

stdin

stdout

1

3
4
1 2 3 4
4 4 1 4
4
4 3 9 10
1 4 4 4
3
14 15 16
10 10 10
15

Ավելացրեց.Հրանտ Հովհաննիսյան
Ամսաթիվ.2014-10-08
Ժամանակի սահմանափակումը.1s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE
Աղբյուրը.West Siberian QF 2014.G

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.