C#でDinic法を実装して最大二部マッチング問題、最大フロー問題を解く

はじめに

atcoderの過去問を解いている際に、最大二部マッチングに帰着できる問題に遭遇した。
C - 2D Plane 2N Points
（なお、この問題自体はグラフ理論の知識無しでも工夫すれば解ける問題だったので、気になった方は考えてみてください）

競技プログラミングでは最大二部マッチング問題は頻出らしいのですが、自分は初心者に毛が生えた程度の実力なので、最大二部マッチング問題であることには気付いたものの対応するデータ構造、アルゴリズムを用意していませんでした。

典型問題だしググれば出てくるだろうと思ったんですが、やはり競技プログラミングでC#erは圧倒的に少数派らしく、コピペで使用できそうなソースコードを見つけることができなかったので、自分で実装したものを残しておくことにします。

最大二部マッチング問題は、最大フロー問題の特殊な場合として扱える。以下の記事が参考になります。
‪実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬

今回使用するDinic法というものは最大フロー問題を高速に解くことができるアルゴリズムで、Ford-Fulkerson法を改善したもの。アルゴリズムの動作原理は以下の記事が詳しい。
tkw's diary - Dinic法

ソースコード

using System;
using System.Collections.Generic;
using System.Linq;

namespace Hoge
{
        class Dinic
    {
        public Dinic(int node_size)
        {
            V = node_size;
            G = Enumerable.Repeat(0, V).Select(_ => new List<Edge>()).ToList();
            level = Enumerable.Repeat(0, V).ToList();
            iter = Enumerable.Repeat(0, V).ToList();
        }

        class Edge
        {
            public Edge(int to, int cap, int rev)
            {
                To = to; Cap = cap; Rev = rev;
            }
            public int To { get; set; }
            public int Cap { get; set; }
            public int Rev { get; set; }
        }

        List<List<Edge>> G;
        int V;
        List<int> level;
        List<int> iter;

        public void AddEdge(int from, int to, int cap)
        {
            G[from].Add(new Edge(to, cap, G[to].Count));
            G[to].Add(new Edge(from, 0, G[from].Count - 1));
        }

        public int MaxFlow(int s, int t)
        {
            int flow = 0;
            while (true)
            {
                BFS(s);
                if (level[t] < 0) { return flow; }
                iter = Enumerable.Repeat(0, V).ToList();
                var f = DFS(s, t, int.MaxValue);
                while (f > 0)
                {
                    flow += f;
                    f = DFS(s, t, int.MaxValue);
                }
            }
        }

        void BFS(int s)
        {
            level = Enumerable.Repeat(-1, V).ToList();
            level[s] = 0;
            var que = new Queue<int>();
            que.Enqueue(s);
            while (que.Count != 0)
            {
                var v = que.Dequeue();
                for (int i = 0; i < G[v].Count; i++)
                {
                    var e = G[v][i];
                    if (e.Cap > 0 && level[e.To] < 0)
                    {
                        level[e.To] = level[v] + 1;
                        que.Enqueue(e.To);
                    }
                }
            }
        }

        int DFS(int v, int t, int f)
        {
            if (v == t) return f;
            for (int i = iter[v]; i < G[v].Count; i++)
            {
                iter[v] = i;
                var e = G[v][i];
                if (e.Cap > 0 && level[v] < level[e.To])
                {
                    var 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;
        }
    }
}

使用法

有向グラフの辺の数だけAddEdgeを呼び出し、辺の始点、終点、フローを与えてやればよいです。MaxFlowが最大フローを返します。

注意点

このソースコードは辺のフローがint型の範囲内のものでしか使用できません。辺のフローがlong型やdouble型の問題に利用したい場合は、EdgeクラスのCapプロパティに対応する部分を書き換える必要があります。C#のジェネリックは数値型のみというような制約が現状ではできないようです。にしてももうちょいうまいやり方なかったのか。式木とか使うとできるみたいなことは聞いたことありますが。

最後に

C#は競プロでの利用者少ないし速度もそんな早くないしでなかなかつらいんだけど、やっぱり好きな言語なのでこれからも使っていきたいです。この記事がC#erの助けになったら嬉しいな。

間違い、改善点等ありましたらコメント等でご指摘いただけると幸いです。