ABC280-F Pay or Receive

問題へのリンク

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("5 5 3");
            WillReturn.Add("1 2 1");
            WillReturn.Add("1 2 2");
            WillReturn.Add("3 4 1");
            WillReturn.Add("4 5 1");
            WillReturn.Add("3 5 2");
            WillReturn.Add("5 3");
            WillReturn.Add("1 2");
            WillReturn.Add("3 1");
            //-2
            //inf
            //nan
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("2 1 1");
            WillReturn.Add("1 1 1");
            WillReturn.Add("1 1");
            //inf
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("9 7 5");
            WillReturn.Add("3 1 4");
            WillReturn.Add("1 5 9");
            WillReturn.Add("2 6 5");
            WillReturn.Add("3 5 8");
            WillReturn.Add("9 7 9");
            WillReturn.Add("3 2 3");
            WillReturn.Add("8 4 6");
            WillReturn.Add("2 6");
            WillReturn.Add("4 3");
            WillReturn.Add("3 8");
            WillReturn.Add("3 2");
            WillReturn.Add("7 9");
            //inf
            //nan
            //nan
            //inf
            //-9
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static long[] GetSplitArr(string pStr)
    {
        return (pStr == "" ? new string[0] : pStr.Split(' ')).Select(pX => long.Parse(pX)).ToArray();
    }

    struct EdgeInfoDef
    {
        internal long ToNode;
        internal long Cost;
    }
    static Dictionary<long, List<EdgeInfoDef>> mEdgeInfoListDict = new Dictionary<long, List<EdgeInfoDef>>();

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

        long[] wkArr = { };
        Action<string> SplitAct = (pStr) => wkArr = GetSplitArr(pStr);

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

        foreach (string EachStr in InputList.Skip(1).Take((int)M)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];
            long Cost = wkArr[2];

            Action<long, long, long> AddEdgeAct = (pFromNode, pToNode, pCost) =>
            {
                if (mEdgeInfoListDict.ContainsKey(pFromNode) == false) {
                    mEdgeInfoListDict[pFromNode] = new List<EdgeInfoDef>();
                }
                EdgeInfoDef WillAdd;
                WillAdd.ToNode = pToNode;
                WillAdd.Cost = pCost;
                mEdgeInfoListDict[pFromNode].Add(WillAdd);
            };
            AddEdgeAct(FromNode, ToNode, +Cost);
            AddEdgeAct(ToNode, FromNode, -Cost);
        }

        var InsUnionFind = new UnionFind();
        for (long I = 1; I <= N; I++) {
            InsUnionFind.MakeSet(I);
        }

        foreach (var EachPair in mEdgeInfoListDict) {
            long FromNode = EachPair.Key;
            foreach (EdgeInfoDef EachEdgeInfo in EachPair.Value) {
                long ToNode = EachEdgeInfo.ToNode;
                InsUnionFind.Unite(FromNode, ToNode);
            }
        }

        // 代表ノードごとにBFS
        var BFSResultDict = new Dictionary<long, BFSResultDef>();
        for (long I = 1; I <= N; I++) {
            long RootNode = InsUnionFind.FindSet(I);
            if (BFSResultDict.ContainsKey(RootNode)) continue;

            BFSResultDef BFSResult = ExecBFS(RootNode);
            BFSResultDict[RootNode] = BFSResult;
        }

        // クエリに回答する
        var sb = new System.Text.StringBuilder();
        foreach (string EachStr in InputList.Skip(1 + (int)M)) {
            SplitAct(EachStr);
            long FromNode = wkArr[0];
            long ToNode = wkArr[1];

            long Root1 = InsUnionFind.FindSet(FromNode);
            long Root2 = InsUnionFind.FindSet(ToNode);
            if (Root1 != Root2) {
                sb.AppendLine("nan");
                continue;
            }
            BFSResultDef BFSResult = BFSResultDict[Root1];
            if (BFSResult.HasCycle) {
                sb.AppendLine("inf");
                continue;
            }

            // ルートに戻る
            long Cost = 0;
            Cost -= BFSResult.CostDict[FromNode];
            Cost += BFSResult.CostDict[ToNode];
            sb.Append(Cost);
            sb.AppendLine();
        }
        Console.Write(sb.ToString());
    }

    class BFSResultDef
    {
        internal bool HasCycle; // コストが正のサイクル有無
        internal Dictionary<long, long> CostDict; // 代表ノードからの距離[代表ノード]
    }

    static BFSResultDef ExecBFS(long pRootNode)
    {
        var WillReturn = new BFSResultDef();

        // 代表ノードからの距離[代表ノード]
        var CostDict = new Dictionary<long, long>();
        CostDict[pRootNode] = 0;

        var Que = new Queue<JyoutaiDef>();
        JyoutaiDef WillEnqueue;
        WillEnqueue.CurrNode = pRootNode;
        WillEnqueue.CostSum = 0;
        Que.Enqueue(WillEnqueue);

        while (Que.Count > 0) {
            JyoutaiDef Dequeued = Que.Dequeue();

            if (mEdgeInfoListDict.ContainsKey(Dequeued.CurrNode)) {
                foreach (EdgeInfoDef EachEdge in mEdgeInfoListDict[Dequeued.CurrNode]) {
                    long NewCost = Dequeued.CostSum + EachEdge.Cost;
                    if (CostDict.ContainsKey(EachEdge.ToNode)) {
                        if (CostDict[EachEdge.ToNode] == NewCost) {
                            continue;
                        }
                        if (CostDict[EachEdge.ToNode] < NewCost) {
                            WillReturn.HasCycle = true;
                            WillReturn.CostDict = null;
                            return WillReturn;
                        }
                    }
                    CostDict[EachEdge.ToNode] = NewCost;
                    WillEnqueue.CurrNode = EachEdge.ToNode;
                    WillEnqueue.CostSum = NewCost;
                    Que.Enqueue(WillEnqueue);
                }
            }
        }

        WillReturn.HasCycle = false;
        WillReturn.CostDict = CostDict;
        return WillReturn;
    }

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

#region UnionFind
// UnionFindクラス
internal class UnionFind
{
    private class NodeInfoDef
    {
        internal long ParentNode;
        internal long Rank;
    }
    private Dictionary<long, NodeInfoDef> mNodeInfoDict =
        new Dictionary<long, NodeInfoDef>();

    // 要素が1つである木を森に追加
    internal void MakeSet(long pNode)
    {
        NodeInfoDef WillAdd = new NodeInfoDef();
        WillAdd.ParentNode = pNode;
        WillAdd.Rank = 0;
        mNodeInfoDict[pNode] = WillAdd;
    }

    // 合併処理
    internal void Unite(long pX, long pY)
    {
        long XNode = FindSet(pX);
        long YNode = FindSet(pY);
        long XRank = mNodeInfoDict[XNode].Rank;
        long YRank = mNodeInfoDict[YNode].Rank;

        if (XRank > YRank) {
            mNodeInfoDict[YNode].ParentNode = XNode;
        }
        else {
            mNodeInfoDict[XNode].ParentNode = YNode;
            if (XRank == YRank) {
                mNodeInfoDict[YNode].Rank++;
            }
        }
    }

    // ノードを引数として、木の根を取得
    internal long FindSet(long pTargetNode)
    {
        // 根までの経路上のノードのList
        var PathNodeList = new List<long>();

        long CurrNode = pTargetNode;
        while (CurrNode != mNodeInfoDict[CurrNode].ParentNode) {
            PathNodeList.Add(CurrNode);
            CurrNode = mNodeInfoDict[CurrNode].ParentNode;
        }

        // 経路圧縮 (親ポインタの付け替え)
        foreach (long EachPathNode in PathNodeList) {
            mNodeInfoDict[EachPathNode].ParentNode = CurrNode;
        }
        return CurrNode;
    }

    internal void DebugPrint()
    {
        foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
            Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
                EachPair.Key, EachPair.Value.ParentNode);
        }
    }
}
#endregion

解説

考察すると

場合1 違う連結成分の場合は、nan
場合2 同じ連結成分で、コストを増加できるサイクルがある場合は、inf
場合3 同じ連結成分で、コストを増加できるサイクルがない場合は、コスト値

場合3では、AからBへの距離は
-1 * (代表ノードからAまでの距離) + (代表ノードからBまでの距離)
と等しいことを使ってます。