ABC434-E Distribute Bunnies

問題へのリンク

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

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

    struct XRInfoDef
    {
        internal int UsagiID;
        internal int X;
        internal int R;
    }
    static List<XRInfoDef> mXRInfoList = new List<XRInfoDef>();

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

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

        int N = int.Parse(InputList[0]);

        var PosSet = new HashSet<int>();

        int CurrUsagiID = 0;
        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            XRInfoDef WillAdd;
            WillAdd.UsagiID = CurrUsagiID++;
            WillAdd.X = wkArr[0];
            WillAdd.R = wkArr[1];
            mXRInfoList.Add(WillAdd);

            PosSet.Add(wkArr[0] - wkArr[1]);
            PosSet.Add(wkArr[0] + wkArr[1]);
        }

        // ノードID[ノード名]なDict
        var PosIDDict = new Dictionary<int, int>();
        foreach (int EachLong in PosSet) {
            PosIDDict[EachLong] = PosIDDict.Count;
        }

        var InsDinic = new Dinic();

        int SourceNode = N + PosSet.Count + 1;
        int SinkNode = N + PosSet.Count + 2;

        // グラフに枝を追加する
        var AppearR = new HashSet<int>();
        foreach (XRInfoDef EachXRInfo in mXRInfoList) {
            int Node1 = EachXRInfo.UsagiID;
            int Node2 = EachXRInfo.X - EachXRInfo.R;
            int Node3 = EachXRInfo.X + EachXRInfo.R;
            Node2 = N + PosIDDict[Node2];
            Node3 = N + PosIDDict[Node3];

            InsDinic.add_edge(SourceNode, Node1, 1);

            InsDinic.add_edge(Node1, Node2, 1);
            InsDinic.add_edge(Node1, Node3, 1);

            if (AppearR.Add(Node2)) {
                InsDinic.add_edge(Node2, SinkNode, 1);
            }
            if (AppearR.Add(Node3)) {
                InsDinic.add_edge(Node3, SinkNode, 1);
            }
        }

        int Answer = InsDinic.max_flow(SourceNode, SinkNode);
        Console.WriteLine(Answer);
    }
}

// Dinic法(蟻本の194ページ)
#region Dinic
internal class Dinic
{
    const int MAX_V = 600000 + 100;

    // 辺を表すクラス
    private class edge
    {
        internal int to;  // 行き先
        internal int cap; // 容量
        internal int rev; // 逆辺
    }

    private List<edge>[] G = new List<edge>[MAX_V]; // グラフの隣接リスト表現
    private int[] level = new int[MAX_V];         // sからの距離
    private int[] iter = new int[MAX_V];          // どこまで調べ終わったか

    // fromからtoへ向かう容量capの辺をグラフに追加する
    internal void add_edge(int from, int to, int cap)
    {
        if (G[from] == null) G[from] = new List<edge>();
        if (G[to] == null) G[to] = new List<edge>();

        var edge1 = new edge();
        edge1.to = to;
        edge1.cap = cap;
        edge1.rev = G[to].Count;
        G[from].Add(edge1);

        var edge2 = new edge();
        edge2.to = from;
        edge2.cap = 0;
        edge2.rev = G[from].Count - 1;
        G[to].Add(edge2);
    }

    // sからの最短距離をBFSで計算する
    private void bfs(int s)
    {
        for (int i = 0; i <= level.GetUpperBound(0); i++) {
            level[i] = -1;
        }
        var que = new Queue<int>();
        level[s] = 0;
        que.Enqueue(s);
        while (que.Count > 0) {
            int v = que.Dequeue();
            for (int i = 0; i < G[v].Count; i++) {
                edge e = G[v][i];
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.Enqueue(e.to);
                }
            }
        }
    }

    // 増加パスをDFSで探す
    private int dfs(int v, int t, int f)
    {
        if (v == t) return f;
        for (; iter[v] < G[v].Count; iter[v]++) {
            edge e = G[v][iter[v]];
            if (e.cap > 0 && level[v] < level[e.to]) {
                int d = dfs(e.to, t, Math.Min(f, e.cap));
                if (d > 0) {
                    e.cap -= d;
                    G[e.to][e.rev].cap += d;
                    return d;
                }
            }
        }
        return 0;
    }

    // sからtへの最大流を求める
    internal int max_flow(int s, int t)
    {
        int flow = 0;
        for (; ; ) {
            bfs(s);
            if (level[t] < 0) return flow;
            Array.Clear(iter, 0, iter.Length);
            int f;
            while ((f = dfs(s, t, int.MaxValue)) > 0) {
                flow += f;
            }
        }
    }
}
#endregion

解説

二部マッチング問題として、dinic法で解いてます。
TLが厳しいので、dinic法でなく、エドモンズ・カープを使うとTLEしました。