ABC210-E Ring MST

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("4 2");
            WillReturn.Add("2 3");
            WillReturn.Add("3 5");
            //11
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("6 1");
            WillReturn.Add("3 4");
            //-1
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    struct ACInfoDef
    {
        internal long A;
        internal long C;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        long[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => long.Parse(pX)).ToArray();

        SplitAct(InputList[0]);
        long N = wkArr[0];

        var ACInfoList = new List<ACInfoDef>();
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            ACInfoDef WillAdd;
            WillAdd.A = wkArr[0];
            WillAdd.C = wkArr[1];
            ACInfoList.Add(WillAdd);
        }

        // クラスカル法を応用して解く
        long CostSum = 0;
        long RootNodeCnt = N;
        bool HasAnswer = false;
        foreach (ACInfoDef EachACInfo in ACInfoList.OrderBy(pX => pX.C)) {
            // 場合1 自己ループなら使わない
            if (EachACInfo.A % RootNodeCnt == 0) continue;

            long NewGCD = DeriveGCD(RootNodeCnt, EachACInfo.A);

            // 場合2 UnionFindのルートノード数と、互いに素の場合
            if (NewGCD == 1) {
                HasAnswer = true;
                CostSum += (RootNodeCnt - 1) * EachACInfo.C;
                break;
            }

            // 場合3 UnionFindのルートノード数の、約数の場合
            long MinusNodeCnt = RootNodeCnt - NewGCD;
            CostSum += MinusNodeCnt * EachACInfo.C;
            RootNodeCnt = NewGCD;
        }

        if (HasAnswer) {
            Console.WriteLine(CostSum);
        }
        else {
            Console.WriteLine(-1);
        }
    }

    // ユークリッドの互除法で2数の最大公約数を求める
    static long DeriveGCD(long pVal1, long pVal2)
    {
        long WarareruKazu = pVal2;
        long WaruKazu = pVal1;

        while (true) {
            long Amari = WarareruKazu % WaruKazu;
            if (Amari == 0) return WaruKazu;
            WarareruKazu = WaruKazu;
            WaruKazu = Amari;
        }
    }
}

解説

クラスカル法でのUnionFindの動きをイメージしつつ

辺をコストの昇順で見ていき、
Aの値が、
場合1 ルートノード数の倍数で自己ループの場合
場合2 ルートノード数と互いに素の場合
場合3 ルートノード数の約数の場合
で場合分けしてます。

場合1なら、その辺はMSTに不要なので飛ばします。
場合2なら、ルートノード数-1 * Costを解に計上して終了です。
場合3なら、ルートノード数を約数の値にして、
           減ったノード数 * Costを解に計上し、ループを継続します。