AOJ 1196 橋の撤去

問題へのリンク

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");
            WillReturn.Add("1 2 3");
            WillReturn.Add("10 20 30");
            WillReturn.Add("10");
            WillReturn.Add("1 2 2 1 5 5 1 8 8");
            WillReturn.Add("10 1 1 20 1 1 30 1 1");
            WillReturn.Add("3");
            WillReturn.Add("1 1");
            WillReturn.Add("1 1");
            WillReturn.Add("0");
            //80
            //136
            //2
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

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

        int CurrInd = 0;
        while (InputList[CurrInd] != "0") {
            int N = int.Parse(InputList[CurrInd]);
            int[] PArr = InputList[CurrInd + 1].Split(' ').Select(pX => int.Parse(pX)).ToArray();
            int[] DArr = InputList[CurrInd + 2].Split(' ').Select(pX => int.Parse(pX)).ToArray();
            Solve(N, PArr, DArr);
            CurrInd += 3;
        }
    }

    struct EdgeInfoDef
    {
        internal int ToNode;
        internal int Cost;
    }

    // 隣接リスト
    static Dictionary<int, List<EdgeInfoDef>> mEdgeListDict = new Dictionary<int, List<EdgeInfoDef>>();

    // 葉ノードのSet
    static HashSet<int> mLeafNodeSet = new HashSet<int>();

    static void Solve(int pN, int[] pPArr, int[] pDArr)
    {
        mEdgeListDict.Clear();
        mLeafNodeSet.Clear();
        for (int I = 0; I <= pPArr.GetUpperBound(0); I++) {
            int FromNode = I + 2;
            int ToNode = pPArr[I];
            int Cost = pDArr[I];

            if (mEdgeListDict.ContainsKey(FromNode) == false) {
                mEdgeListDict[FromNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd1;
            WillAdd1.ToNode = ToNode;
            WillAdd1.Cost = Cost;
            mEdgeListDict[FromNode].Add(WillAdd1);

            if (mEdgeListDict.ContainsKey(ToNode) == false) {
                mEdgeListDict[ToNode] = new List<EdgeInfoDef>();
            }
            EdgeInfoDef WillAdd2;
            WillAdd2.ToNode = FromNode;
            WillAdd2.Cost = Cost;
            mEdgeListDict[ToNode].Add(WillAdd2);
        }

        // 全ての辺のコストの合計
        long AllEdgeCostSum = 0;
        foreach (var EachPair in mEdgeListDict) {
            EachPair.Value.ForEach(pX => AllEdgeCostSum += pX.Cost);
        }
        AllEdgeCostSum /= 2;

        // 葉ノードのSetを求める
        foreach (var EachPair in mEdgeListDict) {
            // 葉ノードである必要十分条件は、出次数が1であること
            if (EachPair.Value.Count == 1) {
                mLeafNodeSet.Add(EachPair.Key);
            }
        }

        // 葉ノードと接続する辺のコストの合計
        long LeafEdgeCostSum = 0;
        foreach (int EachLeafNode in mLeafNodeSet) {
            LeafEdgeCostSum += DeriveLeafConnectNodeCost(EachLeafNode);
        }

        // 全ての葉ノード以外のノードから、葉ノードまでの経路を全探索
        long Answer = long.MaxValue;
        for (int I = 1; I <= pN; I++) {
            if (mLeafNodeSet.Contains(I)) continue;
            long Result = ExecDFS(I);

            long AnswerKouho = 0;
            AnswerKouho += (AllEdgeCostSum - LeafEdgeCostSum) * 3; // 往復コストと削除で3を掛ける
            AnswerKouho += LeafEdgeCostSum; // 葉との接続ノードの分
            AnswerKouho -= Result; // 根から葉までの経路で最適な経路
            Answer = Math.Min(Answer, AnswerKouho);
        }
        Console.WriteLine(Answer);
    }

    // 葉ノードを引数として、接続する辺のコストを返す
    static int DeriveLeafConnectNodeCost(int pLeafNode)
    {
        return mEdgeListDict[pLeafNode][0].Cost;
    }

    struct JyoutaiDef
    {
        internal int CurrNode;
        internal long CostSum;
    }

    // 始点ノードを引数としてDFSを行い、解候補の葉ノードまでの経路を返す
    static long ExecDFS(int pStaNode)
    {
        long WillReturn = long.MinValue;

        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrNode = pStaNode;
        WillPush.CostSum = 0;
        Stk.Push(WillPush);

        var VisitedSet = new HashSet<int>();
        VisitedSet.Add(pStaNode);
        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();

            // 葉ノードの場合
            if (mLeafNodeSet.Contains(Popped.CurrNode)) {
                long CostSum = Popped.CostSum;
                CostSum -= DeriveLeafConnectNodeCost(Popped.CurrNode);
                WillReturn = Math.Max(WillReturn, CostSum);
                continue;
            }

            foreach (EdgeInfoDef EachEdge in mEdgeListDict[Popped.CurrNode]) {
                if (VisitedSet.Add(EachEdge.ToNode)) {
                    WillPush.CurrNode = EachEdge.ToNode;
                    WillPush.CostSum = Popped.CostSum + EachEdge.Cost;
                    Stk.Push(WillPush);
                }
            }
        }
        return WillReturn;
    }
}

解説

まず、葉ノードから開始するのは、明らかに不適だと分かります。

そして、
葉ノード以外のノードを全探索して、最適な葉ノードまでの経路を調べてます。