using System; using System.Collections.Generic; using System.Linq; class Program { static string InputPattern = "Input2"; static List GetInputList() { var WillReturn = new List(); if (InputPattern == "Input1") { WillReturn.Add("4 9"); WillReturn.Add("0 1 1"); WillReturn.Add("0 2 2"); WillReturn.Add("0 3 3"); WillReturn.Add("1 2 4"); WillReturn.Add("1 3 5"); WillReturn.Add("2 3 6"); WillReturn.Add("3 2 100"); WillReturn.Add("2 1 100"); WillReturn.Add("1 0 100"); //300 //3 2 1 0 //と並べた時の300点が最大となる。 //0 1 2 3 //と並べた時、適用される数は6個だが、21点となり、最高点は得られないことに注意せよ。 } else { string wkStr; while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr); } return WillReturn; } struct TokutenDef { internal int Item1; internal int Item2; internal int Score; } static void Main() { List InputList = GetInputList(); int N = int.Parse(InputList[0].Split(' ').First()); int[] wkArr = { }; Action SplitAct = pStr => wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray(); var TokutenList = new List(); foreach (string EachStr in InputList.Skip(1)) { SplitAct(EachStr); TokutenList.Add(new TokutenDef() { Item1 = wkArr[0], Item2 = wkArr[1], Score = wkArr[2] }); } TokutenDef[] TokutenArr = TokutenList.ToArray(); //深さ優先探索で、品物の並びの順列を列挙 List NumArrList = ExecDFS(N); int MaxScoreSum = int.MinValue; foreach (int[] EachNumArr in NumArrList) { //数値ごとの存在する添字のDict var NumIndDict = new Dictionary(); for (int I = 0; I <= EachNumArr.GetUpperBound(0); I++) { NumIndDict[EachNumArr[I]] = I; } int ScoreSum = 0; foreach (TokutenDef EachTokuten in TokutenArr) { if (NumIndDict[EachTokuten.Item1] < NumIndDict[EachTokuten.Item2]) ScoreSum += EachTokuten.Score; } if (MaxScoreSum < ScoreSum) MaxScoreSum = ScoreSum; } Console.WriteLine(MaxScoreSum); } struct JyoutaiDef { internal List NumList; } //深さ優先探索で、品物の並びの順列を列挙 static List ExecDFS(int pN) { var WillReturn = new List(); var stk = new Stack(); JyoutaiDef WillPush; for (int I = 0; I <= pN - 1; I++) { WillPush.NumList = new List { I }; stk.Push(WillPush); } while (stk.Count > 0) { JyoutaiDef Popped = stk.Pop(); if (Popped.NumList.Count == pN) { WillReturn.Add(Popped.NumList.ToArray()); continue; } for (int I = 0; I <= pN - 1; I++) { if (Popped.NumList.Contains(I)) continue; WillPush.NumList = new List(Popped.NumList) { I }; stk.Push(WillPush); } } return WillReturn; } }