AtCoderのABC
次のABCの問題へ
前のABCの問題へ
ABC264-E Blackout 2
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 10");
WillReturn.Add("2 3");
WillReturn.Add("4 10");
WillReturn.Add("5 10");
WillReturn.Add("6 9");
WillReturn.Add("2 9");
WillReturn.Add("4 8");
WillReturn.Add("1 7");
WillReturn.Add("3 6");
WillReturn.Add("8 10");
WillReturn.Add("1 8");
WillReturn.Add("6");
WillReturn.Add("3");
WillReturn.Add("5");
WillReturn.Add("8");
WillReturn.Add("10");
WillReturn.Add("2");
WillReturn.Add("7");
//4
//4
//2
//2
//2
//1
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct UVInfoDef
{
internal int U;
internal int V;
}
static void Main()
{
List<string> InputList = GetInputList();
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();
SplitAct(InputList[0]);
int N = wkArr[0];
int M = wkArr[1];
int E = wkArr[2];
var UVList = new List<UVInfoDef>();
foreach (string EachStr in InputList.Skip(1).Take(E)) {
SplitAct(EachStr);
UVInfoDef WillAdd;
WillAdd.U = wkArr[0];
WillAdd.V = wkArr[1];
UVList.Add(WillAdd);
}
var CutEdgeSet = new HashSet<int>();
var CutEdgeList = new List<int>();
foreach (string EachStr in InputList.Skip(1 + E + 1)) {
int Q = int.Parse(EachStr) - 1;
CutEdgeSet.Add(Q);
CutEdgeList.Add(Q);
}
// UnionFindを用意
var InsUnionFindSizeInfo = new UnionFindSizeInfo();
for (int I = 1; I <= N; I++) {
InsUnionFindSizeInfo.MakeSet(I);
}
for (int I = N + 1; I <= N + M; I++) {
InsUnionFindSizeInfo.MakeSet(I);
}
// 最後まで切断されない枝を接続
for (int I = 0; I <= UVList.Count - 1; I++) {
if (CutEdgeSet.Contains(I) == false) {
InsUnionFindSizeInfo.Unite(UVList[I].U, UVList[I].V);
}
}
// 番号が最大の発電所と、各発電所を接続
for (int I = N + 1; I <= N + M; I++) {
InsUnionFindSizeInfo.Unite(I, N + M);
}
var AnswerList = new List<long>();
for (int I = CutEdgeList.Count - 1; 0 <= I; I--) {
long RootNode = InsUnionFindSizeInfo.FindSet(N + M);
long CurrAnswer = InsUnionFindSizeInfo.GetSize(RootNode);
CurrAnswer -= M;
AnswerList.Add(CurrAnswer);
int TargetEdge = CutEdgeList[I];
InsUnionFindSizeInfo.Unite(UVList[TargetEdge].U, UVList[TargetEdge].V);
}
var sb = new System.Text.StringBuilder();
AnswerList.Reverse();
AnswerList.ForEach(pX => sb.AppendLine(pX.ToString()));
Console.Write(sb.ToString());
}
}
// UnionFindSizeInfoクラス
internal class UnionFindSizeInfo
{
private class NodeInfoDef
{
internal long ParentNode;
internal long Rank;
internal long Size;
}
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;
WillAdd.Size = 1;
mNodeInfoDict[pNode] = WillAdd;
}
// 合併処理
internal void Unite(long pX, long pY)
{
long XNode = FindSet(pX);
long YNode = FindSet(pY);
// 既に同じ木の場合
if (XNode == YNode) return;
long XRank = mNodeInfoDict[XNode].Rank;
long YRank = mNodeInfoDict[YNode].Rank;
if (XRank > YRank) {
mNodeInfoDict[YNode].ParentNode = XNode;
mNodeInfoDict[XNode].Size += mNodeInfoDict[YNode].Size;
}
else {
mNodeInfoDict[XNode].ParentNode = YNode;
mNodeInfoDict[YNode].Size += mNodeInfoDict[XNode].Size;
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 long GetSize(long pNode)
{
long RootNode = FindSet(pNode);
return mNodeInfoDict[RootNode].Size;
}
internal void DebugPrint()
{
foreach (var EachPair in mNodeInfoDict.OrderBy(pX => pX.Key)) {
Console.WriteLine("mNodeInfoDict[{0}].ParentNode={1}",
EachPair.Key, EachPair.Value.ParentNode);
}
}
}
解説
枝の切断は、扱うのが大変なので
クエリを逆から読んで、枝の接続として扱います。
最初に
全てのクエリで切断されない辺を接続します。
次に、
番号が最大の発電所と、各発電所を接続します。
都市が、少なくとも1つの発電所と接続しているかが問題なので
各発電所を接続しても答えに影響はないです。
最後に、クエリの逆順にUniteしてます。