最大フロー(Dinic)のC#実装とTopCoder SRM 442 Div1 Hard

タイトルの通り。

まずは最大フロー(Dinic)の実装。

public static partial class Algorithm {
    public class Edge : IComparable<Edge>
    {
        public int from, to;
        public int length;

        // 今回これは使わない
        public int CompareTo(Edge rhs)
        {
            if (length == rhs.length) return 0;
            return length - rhs.length > 0 ? 1 : -1;
        }

        public Edge(int f, int t, int l)
        {
            from = f;
            to = t;
            length = l;
        }
    }

    public static int MaximumFlow(List<List<Edge>> g, int s, int t)
    {
        int N = g.Count;
        int[,] flow = new int[N, N];
        int[,] cap = new int[N, N];
        int total = 0;

        for (int u = 0; u < N; ++u)
        {
            foreach (Edge e in g[u])
            {
                cap[e.from, e.to] += e.length;
            }
        }

        while (true)
        {
            int[] lv = new int[N];
            Queue<int> Q = new Queue<int>();

            for (int i = 0; i < N; ++i)
            {
                lv[i] = -1;
            }
            lv[s] = 0;
            Q.Enqueue(s);

            for (int d = N; Q.Count > 0 && lv[Q.Peek()] < d; )
            {
                int u = Q.Dequeue();
                if (u == t)
                {
                    d = lv[u];
                }
                foreach (Edge e in g[u])
                {
                    if (cap[u, e.to] - flow[u, e.to] > 0 && lv[e.to] == -1)
                    {
                        Q.Enqueue(e.to);
                        lv[e.to] = lv[u] + 1;
                    }
                }
            }

            bool[] finished = new bool[N];
            bool ok = false;
            for (int f = 1; f > 0; )
            {
                f = AugmentingPath(g, cap, flow, lv, finished, s, t, 2000000000);
                if (f == 0)
                {
                    break;
                }
                total += f;
                ok = true;
            }

            if (!ok)
            {
                break;
            }
        }

        return total;
    }

    private static int AugmentingPath(List<List<Edge>> g, int[,] cap, int[,] flow, int[] lv, bool[] finished, int u, int t, int cur)
    {
        if (u == t || cur == 0)
        {
            return cur;
        }
        if (finished[u])
        {
            return 0;
        }

        finished[u] = true;
        foreach (Edge e in g[u])
        {
            if (lv[e.to] > lv[u])
            {
                int f = AugmentingPath(g, cap, flow, lv, finished, e.to, t, Math.Min(cur, cap[u, e.to] - flow[u, e.to]));
                if (f > 0)
                {
                    flow[u, e.to] += f;
                    flow[e.to, u] -= f;
                    finished[u] = false;
                    return f;
                }
            }
        }

        return 0;
    }
}

これを使ってSRM 442 Div1のHardが解ける。

public class NowhereLand {
    public int placeGuards(string[] cities, int k, string[] guards, string[] agencies) {
        int n = cities.Length;
        bool[,] E = new bool[n, n];
        bool[,] P = new bool[n, k];
        bool[,] C = new bool[n, k];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                E[i, j] = cities[i][j] == '1';
        for (int i = 0; i < n; ++i)
        {
            if (guards[i].Length > 0)
                foreach (int j in
                    Array.ConvertAll<string, int>(guards[i].Split(), int.Parse))
                    P[i, j] = true;
            if (agencies[i].Length > 0)
                foreach (int j in
                    Array.ConvertAll<string, int>(agencies[i].Split(), int.Parse))
                    C[i, j] = true;
        }
        int res = 0;
        for (int w = 0; w < k; ++w)
        {
            List<List<Edge>> g = new List<List<Edge>>();
            for (int i = 0; i < 2 + n; ++i)
            {
                g.Add(new List<Edge>());
            }
            for (int i = 0; i < n; ++i) 
            {
                for (int j = 0; j < n; ++j)
                {
                    if (E[i, j])
                    {
                        g[i].Add(new Edge(i, j, 1));
                    }
                }
                if (P[i, w])
                    g[n].Add(new Edge(n, i, 10000));
                if (!C[i, w])
                    g[i].Add(new Edge(i, n + 1, 10000));
            }
            res += MaximumFlow(g, n, n + 1);
        }
        return res;
    }
}