Custom Min Spanning Tree
1.0.0
يجب أن يطيع بناء شجرة تمتد من بيانات الإدخال هذه القواعد الأساسية الثلاثة:
الصورة 1. مخططات الاتصالات المحتملة بين عقد الرسم البياني. يتم تصوير الاتصالات المحتملة على أنها حواف. يتم تسليط الضوء على الاتصالات التي قد تشكل شجرة الامتداد المطلوبة باللون الأحمر. الحالات أ) ، ب) ، ج) تتوافق مع الأمثلة 1 ، 2 ، 3 أدناه. في بعض الحالات (على سبيل المثال في الحالات B و C) ، قد تفي أكثر من شجرة تمتد بمطالب المشكلة. ومع ذلك ، فإن جميع أشجار الامتداد هذه تشترك في نفس الطول الإجمالي. توضح الحالة أ) أهمية القاعدة 3. توجد أشجار تمتد تحتوي على حواف (1 ، 5) و (5 ، 4) التي تفي القاعدة 2 ولكن لا تفي القاعدة 3 لأن الطول الإجمالي لأي منها هو على الأقل 17.
يتم إعطاء قائمة بجميع الاتصالات الممكنة بين العقد وأطوال الاتصال المعنية. حساب الطول الإجمالي لشجرة الامتداد التي تفي بجميع القواعد الثلاث المقدمة في الوصف.
تم إنشاء مجموعات البيانات للمهمة من قبل معلمي الجامعة التقنية التشيكية للموضوع "الخوارزمية المتقدمة".
يتكون السطر الأول من المدخلات من اثنين من الأعداد الصحيحة N و M مفصولة بالفضاء. القيمة N هي عدد العقد. القيمة M هي عدد الاتصالات المحتملة بين أزواج العقد. بعد ذلك ، هناك خطوط M ، حيث يمثل كل سطر اتصال واحد ممكن. يحتوي الخط على ثلاثة أعداد صحيحة D1 و D2 و L مفصولة بالفضاء ، مما يعني أن طول الاتصال المحتمل بين العقد D1 و D2 يساوي L. يتم ترقيم أجهزة الكشف من 1 إلى N. يتم سرد الاتصالات المحتملة بترتيب عشوائي. يحمل N ≤ 30000 و M ≤ 300000. كل طول على الأقل 10^9.
الإخراج هو سطر واحد يحتوي على الحد الأدنى للطول الإجمالي للشبكة المطلوبة. والنتيجة ليست أكبر من 2^60.
مثال 1 بيانات الإدخال والشبكة الناتجة موضحة في الصورة 1 أ).
مثال 2 بيانات الإدخال والشبكة الناتجة موضحة في الصورة 1 ب).
مثال 2 بيانات الإدخال والشبكة الناتجة موضحة في الصورة 1 ج).
يتم تنفيذ المهمة في Java باستخدام خوارزمية عدوانية Unipized Union (الموضحة هنا). في الخوارزمية ، يتم استخدام نسخة معدلة من HashMap التي تم تنفيذها من قبل المؤلفين Justin Couch و Alex Chaffee و Stephen Colebourne. يستخدم Hashmap هذا الأعداد الصحيحة البدائية فقط وليس كائنات عدد صحيح Java ، مما أدى إلى تحسين الأداء.
