square869120Contest
次のsquare869120Contestの問題へ
前のsquare869120Contestの問題へ
square869120コンテスト1 C問題 お金の街
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("6 6");
WillReturn.Add("1");
WillReturn.Add("2");
WillReturn.Add("3");
WillReturn.Add("4");
WillReturn.Add("5");
WillReturn.Add("7");
WillReturn.Add("1 2");
WillReturn.Add("1 3");
WillReturn.Add("1 6");
WillReturn.Add("2 4");
WillReturn.Add("3 4");
WillReturn.Add("4 5");
//20
}
else if (InputPattern == "Input2") {
WillReturn.Add("4 2");
WillReturn.Add("1");
WillReturn.Add("10");
WillReturn.Add("5");
WillReturn.Add("6");
WillReturn.Add("1 2");
WillReturn.Add("3 4");
//11
}
else if (InputPattern == "Input3") {
WillReturn.Add("5 4");
WillReturn.Add("2");
WillReturn.Add("3");
WillReturn.Add("5");
WillReturn.Add("6");
WillReturn.Add("7");
WillReturn.Add("1 3");
WillReturn.Add("1 4");
WillReturn.Add("2 4");
WillReturn.Add("4 5");
//20
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
static long[] mDArr;
// 隣接リスト
static Dictionary<long, List<long>> mToNodeListDict = new Dictionary<long, List<long>>();
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];
long K = wkArr[1];
mDArr = InputList.Skip(1).Take((int)N).Select(pX => long.Parse(pX)).ToArray();
foreach (string EachStr in InputList.Skip(1 + (int)N)) {
SplitAct(EachStr);
long FromNode = wkArr[0];
long ToNode = wkArr[1];
if (mToNodeListDict.ContainsKey(FromNode) == false) {
mToNodeListDict[FromNode] = new List<long>();
}
if (mToNodeListDict.ContainsKey(ToNode) == false) {
mToNodeListDict[ToNode] = new List<long>();
}
mToNodeListDict[FromNode].Add(ToNode);
mToNodeListDict[ToNode].Add(FromNode);
}
var ResultList = new List<long>();
for (long I = 1; I <= N; I++) {
ResultList.Add(ExecDFS(I));
}
Console.WriteLine(ResultList.Max());
}
struct JyoutaiDef
{
internal long CurrNode;
internal long VisitedSet;
internal long ScoreSum;
}
// 始点を引数として、DFSを行う
static long ExecDFS(long pStaNode)
{
long WillReturn = long.MinValue;
var Stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.CurrNode = pStaNode;
WillPush.VisitedSet = (1L << (int)pStaNode);
WillPush.ScoreSum = mDArr[pStaNode - 1];
Stk.Push(WillPush);
while (Stk.Count > 0) {
JyoutaiDef Popped = Stk.Pop();
WillReturn = Math.Max(WillReturn, Popped.ScoreSum);
if (mToNodeListDict.ContainsKey(Popped.CurrNode)) {
foreach (long EachToNode in mToNodeListDict[Popped.CurrNode]) {
long CurrBit = (1L << (int)EachToNode);
if ((Popped.VisitedSet & CurrBit) > 0) continue;
WillPush.VisitedSet = Popped.VisitedSet | CurrBit;
WillPush.CurrNode = EachToNode;
WillPush.ScoreSum = Popped.ScoreSum + mDArr[EachToNode - 1];
Stk.Push(WillPush);
}
}
}
return WillReturn;
}
}
解説
全ての始点からのDFSを試してます。
ノード数は50以下なので
long型のBitSetで再訪を防止してます。