Module: امتداد الأشجار: خوارزمية Kruskal

Problem

تقع Besi على شبكة من القمم N (2 & le؛ N & le؛ 10 ⁵ ) معنونة 1 & hellip؛ N و 2N بوابتين معنون 1 & hellip؛ 2N. تربط كل بوابة رأسين مختلفين u و v (u & ne ؛ v). يمكن لمجموعة من البوابات أن تربط بعض زوج من الرؤوس.
كل رأس v متاخم لأربعة بوابات مختلفة. يتم إعطاء قائمة بوابات v بواسطة pv = [p _{v، 1} ، p _{v، 2} ، p _{v، 3} ، p < sub> v، 4 ].

يمكن تمثيل موقعك الحالي بزوج مرتب (الرأس الحالي ، البوابة الحالية) ؛ أي زوج (v، p _{v، i} ) حيث 1 & le؛ v & le؛ N and 1 & le؛ i & le؛ 4. يمكنك استخدام إحدى العمليات التالية لتغيير موقعك الحالي:

قم بتغيير الرأس الحالي عن طريق التحرك خلال البوابة الحالية.
تبديل البوابة الحالية. في كل قمة ، يتم إقران أول بوابتين في القائمة ويتم أيضًا إقران آخر بوابتين في القائمة. لذلك إذا كانت حالتك الحالية هي (v ، p _{v ، 2} ) ، فيمكنك التبديل لاستخدام البوابة (v ، p _{v ، 1} ) والعكس. وبالمثل ، إذا كان موقعك الحالي هو (v، p _{v، 3} ) يمكنك التبديل إلى البوابة (v، p _{v، 4} ) والعودة. لا يُسمح بأي تبديل آخر (على سبيل المثال ، لا يمكنك التبديل من portal pv ، 2 إلى portal) p _{v، 4} ).
هناك 4N ولايات مختلفة في المجموع. لسوء الحظ ، قد لا يكون من الممكن الوصول إلى أي دولة من أي دولة من خلال سلسلة من العمليات المحددة. لذلك ، بالنسبة لتكلفة cv (1 & le؛ c _v & le؛ 1000) ، يمكنك إعادة ترتيب قائمة البوابات المجاورة لـ v ، بأي ترتيب تريده. بعد ذلك ، يتم دمج أول بوابتين في القائمة في زوج واحد ، والبابين الأخيرين في زوج آخر.

على سبيل المثال ، إذا قمت بإعادة ترتيب بوابات v بالترتيب [p _{v، 3} ، p _{v، 1} ، p _{v، 2} ، p _{v، 4} ] هذا يعني. ماذا لو كنت في القمة v ،

إذا كنت في البوابة p _{v ، 1} ، يمكنك التبديل إلى البوابة p _{v ، 3} والعودة
إذا كنت في البوابة p _{v ، 2} ، يمكنك التبديل إلى p _{v ، 4} البوابة والعودة
الآن لا يمكنك التبديل من البوابة p _{v ، 1} إلى p _{v ، 2} ، أو من البوابة p _{v ، 3} إلى البوابة p _{الخامس ، 4} والعكس.
احسب الحد الأدنى لعدد الأقمار المطلوبة لتعديل الشبكة بطريقة تجعل كل حالة قابلة للوصول من كل دولة. من المضمون أن يتم إنشاء بيانات الاختبار بحيث توجد طريقة واحدة على الأقل لتعديل الشبكة بهذه الطريقة.

الإدخال: & nbsp؛
يحتوي السطر الأول على N.
يصف كل سطر من السطور N التالية قمة الرأس. السلسلة v + 1 تحتوي على 5 أعداد صحيحة مفصولة بمسافات c _v ، p _{v، 1} ، p _{v، 2} ، p _{v ، 3} ، p _{v، 4} .
مضمون أنه لكل v all p _{v ، 1} ، p _{v ، 2} ، p _{v ، 3} ، p _{v ، 4} مميزة ، وكل بوابة تظهر في قوائم رأسين بالضبط.

الإخراج: & nbsp؛
يحتوي سطر واحد على الحد الأدنى من عدد الأقمار المطلوب لتعديل الشبكة لجعل كل حالة قابلة للوصول من حالة أخرى.
نبسب ؛

أمثلة <الجسم>

#	إدخال	الإخراج	الشرح
1	5 10 1 4 8 9 11 1 2 5 6 12 9 10 2 3 3 4 3 6 7 15 10 8 7 5 نبسب ؛	13	يكفي تبديل قوائم الرؤوس 1 و 4. وهذا يتطلب c1 + c4 = 13 muns. التبديلات هي: p1 = [1،9،4،8] و p4 = [7،4،6،3].