B69 Black Company 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("2 1");
            WillReturn.Add("111111111111000000000000");
            WillReturn.Add("000000000000111111111111");
            //No
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("10 2");
            WillReturn.Add("101001000011000100010111");
            WillReturn.Add("000010011110110010100111");
            WillReturn.Add("101110001110000011110111");
            WillReturn.Add("011011110100011110100011");
            WillReturn.Add("000011001111111010110001");
            WillReturn.Add("001010011010101010110100");
            WillReturn.Add("001010010111101101111010");
            WillReturn.Add("110011111100010110111011");
            WillReturn.Add("100010011100011101110001");
            WillReturn.Add("010110100101101111111011");
            //Yes
        }
        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();
    }

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

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

        char[,] BanArr = CreateBanArr(InputList.Skip(1));
        long UB_X = BanArr.GetUpperBound(0);
        long UB_Y = BanArr.GetUpperBound(1);

        var NodeNameList = new List<string>();
        NodeNameList.Add("Source");
        NodeNameList.Add("Sink");

        for (long Y = 0; Y <= UB_Y; Y++) {
            NodeNameList.Add("N" + Y.ToString());
        }

        for (long X = 0; X <= UB_X; X++) {
            NodeNameList.Add("Time" + X.ToString());
        }

        // ノードID[ノード名]なDict
        var NodeIDDict = new Dictionary<string, int>();
        foreach (string EachStr in NodeNameList) {
            NodeIDDict[EachStr] = NodeIDDict.Count;
        }

        var InsDinic = new Dinic(NodeNameList.Count);

        for (long I = 0; I <= UB_Y; I++) {
            InsDinic.add_edge(NodeIDDict["Source"], NodeIDDict["N" + I.ToString()], 10);
        }

        for (long X = 0; X <= UB_X; X++) {
            for (long Y = 0; Y <= UB_Y; Y++) {
                if (BanArr[X, Y] == '1') {
                    InsDinic.add_edge(NodeIDDict["N" + Y.ToString()], NodeIDDict["Time" + X.ToString()], 1);
                }
            }
        }

        for (long X = 0; X <= UB_X; X++) {
            InsDinic.add_edge(NodeIDDict["Time" + X.ToString()], NodeIDDict["Sink"], M);
        }

        long Answer = InsDinic.max_flow(NodeIDDict["Source"], NodeIDDict["Sink"]);
        if (Answer == M * 24) {
            Console.WriteLine("Yes");
        }
        else {
            Console.WriteLine("No");
        }
    }

    ////////////////////////////////////////////////////////////////
    // IEnumerable<string>をcharの2次元配列に設定
    ////////////////////////////////////////////////////////////////
    static char[,] CreateBanArr(IEnumerable<string> pStrEnum)
    {
        var StrList = pStrEnum.ToList();
        if (StrList.Count == 0) {
            return new char[0, 0];
        }
        int UB_X = StrList[0].Length - 1;
        int UB_Y = StrList.Count - 1;

        char[,] WillReturn = new char[UB_X + 1, UB_Y + 1];

        for (int Y = 0; Y <= UB_Y; Y++) {
            for (int X = 0; X <= UB_X; X++) {
                WillReturn[X, Y] = StrList[Y][X];
            }
        }
        return WillReturn;
    }
}

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

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

    // コンストラクタ(グラフのノード数を指定)
    internal Dinic(long pGraphNodeCnt)
    {
        G = new List<edge>[pGraphNodeCnt + 1];
        level = new long[pGraphNodeCnt + 1];
        iter = new long[pGraphNodeCnt + 1];
    }

    // fromからtoへ向かう容量capの辺をグラフに追加する
    internal void add_edge(long from, long to, long 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(long s)
    {
        for (long i = 0; i <= level.GetUpperBound(0); i++) {
            level[i] = -1;
        }
        var que = new Queue<long>();
        level[s] = 0;
        que.Enqueue(s);
        while (que.Count > 0) {
            long v = que.Dequeue();
            for (long i = 0; i < G[v].Count; i++) {
                edge e = G[v][(int)i];
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    que.Enqueue(e.to);
                }
            }
        }
    }

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

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

解説

Sourceから各人に容量10の辺を貼り
各人の可能な時間に容量1の辺を貼り
各時間からSinkに容量Mの辺を貼り
M * 24 のフローが実現できるかを判定してます。