GRL_2_B: Minimum-Cost Arborescence

問題へのリンク

C#のソース

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

// Q055 最小全域有向木 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_2_B&lang=jp
class Program
{
    static string InputPattern = "InputX";

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

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

    static HashSet<int> mNodeSet = new HashSet<int>(); // 頂点のSet
    static int mRootNode; // 根ノード

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

    // 隣接グラフ(正方向)
    static Dictionary<int, List<EdgeInfoDef>> mSeiEdgeListDict = new Dictionary<int, List<EdgeInfoDef>>();

    // 隣接グラフ(逆方向)
    static Dictionary<int, List<EdgeInfoDef>> mRevEdgeListDict;

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

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

        SplitAct(InputList[0]);
        int mV = wkArr[0];
        for (int I = 0; I <= mV - 1; I++) {
            mNodeSet.Add(I);
        }
        mRootNode = wkArr[2];

        foreach (int EachNode in mNodeSet) {
            mSeiEdgeListDict[EachNode] = new List<EdgeInfoDef>();
        }

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            int s = wkArr[0];
            int e = wkArr[1];
            int Cost = wkArr[2];

            mSeiEdgeListDict[s].Add(new EdgeInfoDef() { ToNode = e, Cost = Cost });
        }
        // 正辺の隣接グラフから逆辺の隣接グラフを作成
        mRevEdgeListDict = CreateRevEdgeListDict(mSeiEdgeListDict);

        Solve();
    }

    // 正辺の隣接グラフから逆辺の隣接グラフを作成
    static Dictionary<int, List<EdgeInfoDef>> CreateRevEdgeListDict(
        Dictionary<int, List<EdgeInfoDef>> pSeiEdgeListDict)
    {
        var RevEdgeListDict = new Dictionary<int, List<EdgeInfoDef>>();

        foreach (int EachNode in mNodeSet) {
            RevEdgeListDict[EachNode] = new List<EdgeInfoDef>();
        }

        foreach (var EachPair in pSeiEdgeListDict) {
            foreach (EdgeInfoDef EachEage in EachPair.Value) {
                EdgeInfoDef WillAdd;
                WillAdd.ToNode = EachPair.Key;
                WillAdd.Cost = EachEage.Cost;
                RevEdgeListDict[EachEage.ToNode].Add(WillAdd);
            }
        }

        return RevEdgeListDict;
    }

    static int mAnswerCost = 0;

    static void Solve()
    {
        // 選択した枝の隣接グラフ(正方向)
        var SelectedSeiEdgeListDict = new Dictionary<int, List<EdgeInfoDef>>();

        foreach (int EachNode in mNodeSet) {
            SelectedSeiEdgeListDict[EachNode] = new List<EdgeInfoDef>();
        }

        foreach (int EachNode in mNodeSet) {
            // 根ノードの場合
            if (EachNode == mRootNode) continue;

            // 最小コストな入次辺を選択する。
            int MinCost = int.MaxValue;
            int MinNode = -1;
            foreach (EdgeInfoDef EachEdge in mRevEdgeListDict[EachNode]) {
                if (MinCost > EachEdge.Cost) {
                    MinCost = EachEdge.Cost;
                    MinNode = EachEdge.ToNode;
                }
            }
            SelectedSeiEdgeListDict[MinNode].Add(new EdgeInfoDef() { ToNode = EachNode, Cost = MinCost });
        }

        // 選択した枝の隣接グラフ(逆方向)
        var SelectedRevEdgeListDict = CreateRevEdgeListDict(SelectedSeiEdgeListDict);

        // 強連結成分分解を行い、強連結成分分解の配列のListを返す
        HashSet<int> SCCNodeSet = DeriveSCCNodeSet(SelectedSeiEdgeListDict, SelectedRevEdgeListDict);

        if (SCCNodeSet == null) {
            foreach (int EachNode in mNodeSet) {
                foreach (EdgeInfoDef EachEdge in SelectedSeiEdgeListDict[EachNode]) {
                    mAnswerCost += EachEdge.Cost;
                }
            }
            // 解の出力
            Console.WriteLine(mAnswerCost);
            return;
        }

        // 強連結成分の全てのノード入次辺のコストを集計
        foreach (int EachSCCNode in SCCNodeSet) {
            foreach (EdgeInfoDef EachEdge in SelectedSeiEdgeListDict[EachSCCNode]) {
                if (SCCNodeSet.Contains(EachEdge.ToNode)) {
                    mAnswerCost += EachEdge.Cost;
                }
            }
        }

        // NewNodeは、最大値+1とする
        int NewNode = mNodeSet.Max() + 1;

        mSeiEdgeListDict[NewNode] = new List<EdgeInfoDef>();

        foreach (int EachSCCNode in SCCNodeSet) {
            // 合併前ノードと合併後ノードを引数として、合併後ノードから出次辺を引く
            CreateOutEdge(SCCNodeSet, EachSCCNode, NewNode);

            // サイクル内の入次辺のコスト
            int CycleEdgeCost = SelectedRevEdgeListDict[EachSCCNode][0].Cost;

            // 合併前ノードと合併後ノードを引数として、合併後ノードに入次辺を引く
            CreateInEdge(SCCNodeSet, EachSCCNode, NewNode, CycleEdgeCost);
        }

        // SCCの辺を削除
        foreach (int EachSCCNode in SCCNodeSet) {
            mSeiEdgeListDict.Remove(EachSCCNode);
        }
        foreach (var EachPair in mSeiEdgeListDict) {
            var pList = EachPair.Value;
            for (int I = pList.Count - 1; 0 <= I; I--) {
                if (SCCNodeSet.Contains(pList[I].ToNode)) {
                    pList.RemoveAt(I);
                }
            }
        }

        // 頂点のSetの更新
        mNodeSet.Add(NewNode);
        mNodeSet.ExceptWith(SCCNodeSet);

        // 正辺の隣接グラフから逆辺の隣接グラフを作成
        mRevEdgeListDict = CreateRevEdgeListDict(mSeiEdgeListDict);

        // 再帰呼び出し
        Solve();
    }

    // 合併前ノードと合併後ノードを引数として、合併後ノードから出次辺を引く
    static void CreateOutEdge(HashSet<int> pSCCNodeSet, int pBeforeNode, int pAfterNode)
    {
        foreach (EdgeInfoDef EachEdge in mSeiEdgeListDict[pBeforeNode]) {
            if (pSCCNodeSet.Contains(EachEdge.ToNode) == false) {
                mSeiEdgeListDict[pAfterNode].Add(EachEdge);
            }
        }
    }

    // 合併前ノードと合併後ノードを引数として、合併後ノードに入次辺を引く
    static void CreateInEdge(HashSet<int> pSCCNodeSet, int pBeforeNode, int pAfterNode, int pCycleEdgeCost)
    {
        var FromNodeSet = new HashSet<int>();
        foreach (EdgeInfoDef EachEdge in mRevEdgeListDict[pBeforeNode]) {
            if (pSCCNodeSet.Contains(EachEdge.ToNode)) continue;
            FromNodeSet.Add(EachEdge.ToNode);
        }

        foreach (int EachFromNode in FromNodeSet) {
            foreach (int EachKey in mSeiEdgeListDict.Keys.ToArray()) {
                if (EachKey != EachFromNode) continue;
                foreach (EdgeInfoDef EachEdge in mSeiEdgeListDict[EachKey].ToArray()) {
                    if (EachEdge.ToNode != pBeforeNode) continue;
                    EdgeInfoDef WillAdd;
                    WillAdd.ToNode = pAfterNode;
                    WillAdd.Cost = EachEdge.Cost - pCycleEdgeCost;
                    mSeiEdgeListDict[EachKey].Add(WillAdd);
                }
            }
        }
    }

    // 強連結成分分解を行い、
    // 強連結成分があれば、Setを返す
    // 強連結成分がなければ、nullを返す
    static HashSet<int> DeriveSCCNodeSet(
        Dictionary<int, List<EdgeInfoDef>> pSelectedSeiEdgeListDict,
        Dictionary<int, List<EdgeInfoDef>> pSelectedRevEdgeListDict)
    {
        // それぞれの深さ優先探索での、訪問済ノードの管理用
        var VisitedSet = new HashSet<int>();

        // DFSツリーでの訪問順(帰りがけ順)。 帰りがけ順[ノードID]なDict
        var PostNumDict = new Dictionary<int, int>();

        int Timer = 1;

        // 処理01 深さ優先探索を行い、帰りがけで番号を振る
        foreach (int EachNode in mNodeSet) {
            ExecDFS1(EachNode, VisitedSet, PostNumDict, ref  Timer, pSelectedSeiEdgeListDict);
        }

        // ノード[帰りがけでの番号]なDict
        var PostNumIndDict = new Dictionary<int, int>();
        foreach (var EachPair in PostNumDict) {
            PostNumIndDict[EachPair.Value] = EachPair.Key;
        }

        // 訪問済ノードの初期化
        VisitedSet.Clear();

        foreach (var EachPair in PostNumIndDict.OrderByDescending(pX => pX.Key)) {
            if (VisitedSet.Contains(EachPair.Value)) continue;

            HashSet<int> SCCNodeSet = ExecDFS2(EachPair.Value, VisitedSet, pSelectedRevEdgeListDict);
            if (SCCNodeSet.Count > 1) {
                return SCCNodeSet;
            }
        }

        return null;
    }

    // 処理01 深さ優先探索を行い、帰りがけで番号を振る
    static void ExecDFS1(int pCurr, HashSet<int> pVisitedSet,
        Dictionary<int, int> pPostNumDict, ref int pTimer,
        Dictionary<int, List<EdgeInfoDef>> pSelectedSeiEdgeListDict)
    {
        if (pVisitedSet.Add(pCurr) == false) return;

        foreach (EdgeInfoDef EachEdge in pSelectedSeiEdgeListDict[pCurr]) {
            ExecDFS1(EachEdge.ToNode, pVisitedSet, pPostNumDict, ref pTimer, pSelectedSeiEdgeListDict);
        }
        pPostNumDict[pCurr] = pTimer++;
    }

    struct JyoutaiDef
    {
        internal int CurrNode;
    }

    // 処理02 枝の向きを反転して、深さ優先探索を行う
    static HashSet<int> ExecDFS2(int pStaNode, HashSet<int> pVisitedSet,
        Dictionary<int, List<EdgeInfoDef>> pSelectedRevEdgeListDict)
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrNode = pStaNode;
        Stk.Push(WillPush);

        var SCCNodeSet = new HashSet<int>();
        pVisitedSet.Add(pStaNode);

        while (Stk.Count > 0) {
            JyoutaiDef Popped = Stk.Pop();
            SCCNodeSet.Add(Popped.CurrNode);
            pVisitedSet.Add(Popped.CurrNode);

            foreach (EdgeInfoDef EachEdge in pSelectedRevEdgeListDict[Popped.CurrNode]) {
                if (pVisitedSet.Contains(EachEdge.ToNode)) continue;

                WillPush.CurrNode = EachEdge.ToNode;
                Stk.Push(WillPush);
            }
        }
        return SCCNodeSet;
    }
}

解説

下記の
Edmonds / Chu-Liu のアルゴリズムで解いてます。

処理01 最初に、根以外の各ノードで最小の入次辺を選択します。
処理02 強連結成分分解を行います。
       (2ノード以上な強連結成分があれば、閉路です)
処理03 閉路が無かったら、それが最小全域有向木です。
処理04 閉路があったら、1つの頂点にまとめ出次辺と入次数を設定します。
       (この頂点への強連結成分以外からの入次辺のコストは、
        この頂点への強連結成分での入次辺のコストを引いて設定します)
処理05 処理01に戻ります。

最小有向全域木を求める | Chu-Liu/Edmonds' algorithm