1. はじめに

　競技プログラミングで最大流、最小カット、マッチング、最小費用流などのフローを流す問題をまとめたものです(千個はありません)。
　メインは問題をまとめることであり、サブとして簡単な解き方・方針をつけています。ネタバレとなってしまっている点は注意です。詳細な解説は元のサイトの解説をご覧ください。また、フローのアルゴリズムの中身そのものは他の素晴らしい文献をご参照ください。

コードについての補足

　C++のコードを付けている場合、以下のネットワークフローライブラリ(Ford-Fulkerson, Dinic algorithm, 最小費用流)が張り付けられています。自作なのでバグがある可能性もあります。今のところ、問題なくACできていますが、バグがありましたら教えていただけますとありがたいです。最大流がintで収まらない場合はlong longに型を取りなおしてください。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)

template<class T>
using vi = vector<T>;

template<class T>
using vii = vector<vi<T>>;

template<class T>
using viii = vector<vii<T>>;

//NAMIDAIRO自作フローライブラリ
struct FF {
    struct edge {
        int to, rev, cost;
        edge(int t = 0, int r = 0, int c = 0) : to(t), rev(r), cost(c){}
    };

    int n;
    vii<edge> to;

    FF(int n_) : n(n_), to(n_){}

    void addedge(int v, int u, int cost) {
        int sv = (int)to[v].size();
        int su = (int)to[u].size();

        to[v].push_back({ u, su, cost });
        to[u].push_back({ v, sv, 0 });
    }

    int dfs(int v, int t, int f, vi<bool> &visited) {
        if (v == t) return f;
        visited[v] = true;
        for (edge &nv : to[v]) {
            if (visited[nv.to] || nv.cost == 0) continue;
            int res = dfs(nv.to, t, min(f, nv.cost), visited);
            if (res > 0) {
                nv.cost -= res;
                to[nv.to][nv.rev].cost += res;
                return res;
            }
        }
        return 0;
    }

    int maxflow(int s, int t) {
        int res = 0, flow = 0;
        do {
            flow = 1e9;
            vi<bool> visited(n);
            flow = dfs(s, t, flow, visited);
            res += flow;
        } while (flow);
        return res;
    }

};

struct Dinic {
    struct edge {
        int to, rev; ll cap;
        edge(int t = 0, int r = 0, ll c = 0) : to(t), rev(r), cap(c) {}
    };

    int n;
    vii<edge> to;
    vi<int> iter;
    vi<int> dist;

    Dinic(int n_ = 0) : n(n_), to(n_), iter(n_), dist(n_) {}

    void addedge(int u, int v, ll cap) {
        int su = (int)to[u].size();
        int sv = (int)to[v].size();
        to[u].push_back({ v, sv, cap });
        to[v].push_back({ u, su, 0 });
    }

    void bfs(int s) {
        dist.assign(n, -1);
        dist[s] = 0;
        queue<int> q;
        q.push(s);

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (edge& nv : to[v]) {
                if (dist[nv.to] >= 0 || nv.cap == 0) continue;
                dist[nv.to] = dist[v] + 1;
                q.push(nv.to);
            }
        }
    }

    ll dfs(int v, int t, ll f = 1e18) {
        if (v == t) return f;
        int sv = (int)to[v].size();
        for (int& i = iter[v]; i < sv; i++) {
            edge& nv = to[v][i];
            if (dist[nv.to] <= dist[v] || nv.cap == 0) continue;
            ll nf = dfs(nv.to, t, min(f, nv.cap));
            if (nf > 0) {
                nv.cap -= nf;
                to[nv.to][nv.rev].cap += nf;
                return nf;
            }
        }
        return 0;
    }

    ll maxflow(int s, int t) {
        ll res = 0, flow = 0;
        while (true) {
            bfs(s);
            if (dist[t] < 0) break;
            iter.assign(n, 0);
            while (flow = dfs(s, t)) res += flow;
        }
        return res;
    }
};


struct MCF {
private:
    const long long inf = 1e18;
    vector<long long> dist;       //最短距離(費用)
    vector<int> pv, pe;     //直前の頂点、辺    

public:
    struct edge {
        int to, rev; long long cap, cost;
        edge(int t = 0, int r = 0, long long ca = 0, long long co = 0)
            : to(t), rev(r), cap(ca), cost(co) {}
    };

    struct pii {
        long long d; int v; //最短距離(費用)、頂点番号
        pii(long long d_ = 0, int v_ = 0) : d(d_), v(v_) {}

        bool operator<(const pii& other) const {
            if (d != other.d) return d < other.d;
            return v < other.v;
        }

        bool operator>(const pii& other) const {
            if (d != other.d) return d > other.d;
            return v > other.v;
        }
    };

    int n;
    vector<vector<edge>> to;
    vector<long long> pot;        //ポテンシャル

    MCF(int n_ = 1) : n(n_), to(n_), pot(n_), dist(n_), pv(n_), pe(n_) {}

    void addedge(int u, int v, long long cap, long long cost) {
        int su = (int)to[u].size();
        int sv = (int)to[v].size();
        to[u].push_back({ v, sv, cap, cost });
        to[v].push_back({ u, su, 0, -cost });
    }

    //s->tへ流量fの最小費用流、流せないときは-1
    long long mincostflow(int s, int t, long long f) {
        long long res = 0;
        pot.assign(n, 0);
        while (f) {
            priority_queue<pii, vector<pii>, greater<pii>> pq;
            dist.assign(n, inf);
            dist[s] = 0;
            pq.push({ 0, s });
            while (!pq.empty()) {
                pii elem = pq.top();
                pq.pop();
                if (dist[elem.v] < elem.d) continue;
                int sv = (int)to[elem.v].size();
                for (int i = 0; i < sv; i++) {
                    edge& nv = to[elem.v][i];
                    if (nv.cap == 0 || dist[nv.to] + pot[nv.to] <= dist[elem.v] + pot[elem.v] + nv.cost) continue;
                    dist[nv.to] = dist[elem.v] + pot[elem.v] - pot[nv.to] + nv.cost;
                    pv[nv.to] = elem.v;
                    pe[nv.to] = i;
                    pq.push({ dist[nv.to], nv.to });
                }
            }

            if (dist[t] == inf) return -1; //流せる最小費用流が存在しない

            for (int v = 0; v < n; v++) pot[v] += dist[v];

            long long nf = f;
            for (int v = t; v != s; v = pv[v]) nf = min(nf, to[pv[v]][pe[v]].cap);
            f -= nf;
            res += nf * (pot[t] - pot[s]); //pot[s] = 0で不要だがポテンシャルを明確化する
            for (int v = t; v != s; v = pv[v]) {
                edge& nv = to[pv[v]][pe[v]];
                nv.cap -= nf;
                to[v][nv.rev].cap += nf;
            }
        }
        return res;
    }
};

verify用の問題

　自作ライブラリを使う方は以下のverify用の問題で通してから取り組むとよいと思います。

最大流(GRL_6_A)
最小費用流(GRL_6_B)
2部マッチング(GRL_7_A)

参考文献

問題を探すのにあたり、活用させていただいたサイトです。

AtCoder Tags
AtCoder 版！蟻本 (中級編)

2. フローの問題一覧

2.1. 最大流・最小カット

QUPC2014H お風呂は気持ちいい

　始点を設定し、始点から石の近くにいる魔法使いへinfの流量の辺を張る。あとは魔法使いから魔法使いへ辺を張り、フローを流して最大流と必要魔力量を比較する。

コード

int main()
{
    int n, m, p, g;
    cin >> n >> m >> p >> g;
    Dinic mf(m + 1);
    const ll inf = 1e18;
    rep(i, g) {
        int l;
        cin >> l;
        mf.addedge(m, l, inf);
    }

    rep(i, n) {
        int f, t, c;
        cin >> f >> t >> c;
        mf.addedge(f, t, c);
    }

    ll res = mf.maxflow(m, 0);
    cout << (res >= p ? "Yes" : "No") << endl;
    return 0;
}

全く関係ない余談

　「アスナさん」、「お風呂」でSAOのオーディナルスケールを連想しましたが、映画は2017年なので関係ないか。。と思っていましたら、やはり元ネタだったようです。にわかでした。

解説でのコメント

KUPC2016 E 柵

　最小カットに帰着させる。見ているマスに対し、上下左右の”.”のマスへ辺を張るが、マス同士の辺のカットではなく、頂点のカットにしたいため、入り口側のマスと出口側のマスを作り、その間は容量1の辺を張る。始点からXへ容量infの辺、外周部の"."マスから終点へ容量1の辺を張る。フローを流したときの最大流(最小カット)が答え。

コード

int main()
{
    int h, w;
    cin >> h >> w;
    vi<string> s(h);
    rep(i, h) cin >> s[i];

    FF ff(h * w * 2 + 2);
    
    int S = h * w * 2, T = h * w * 2 + 1;
    auto conv = [&](int i, int j) {
        return w * i + j;
    };
    auto conv2 = [&](int i, int j) {
        return h * w + w * i + j;
    };

    int dx[] = { 1, 0, -1, 0 };
    int dy[] = { 0, 1, 0, -1 };
    rep(i, h) rep(j, w) {
        if (s[i][j] == 'X') ff.addedge(S, conv2(i, j), 1e9);
        ff.addedge(conv(i, j), conv2(i, j), 1);

        rep(k, 4) {
            int ni = i + dx[k];
            int nj = j + dy[k];
            if (ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
            ff.addedge(conv2(i, j), conv(ni, nj), 1);
        }
        

        if (i == 0 || j == 0 || i == h - 1 || j == w - 1) {
            ff.addedge(conv2(i, j), T, 1);
            if (s[i][j] == 'X') {
                cout << -1 << endl;
                return 0;
            }
        }
    }

    ll res = ff.maxflow(S, T);
    cout << res << endl;
    return 0;
}

2.2. マッチング

　グリッド問題でのマッチングのときの典型的な考え方です。

グリッドに関する問題はしばしば二部グラフにして考えることが有効ですが、2 つのパターンをよく見る気がします:

左ノードが x 座標、右ノードが y 座標に対応して、各マス (x, y) は左右を結ぶ辺に対応する (Asteroids はこっち)

グリッドグラフは市松模様に塗ると二部グラフである

AtCoder 版！蟻本 (中級編)より引用

ALPC D Maxflow

市松模様の二部グラフにする典型テクを使う。隣接マス同士で辺を張り、最大マッチングを求める。残余グラフの各辺の容量を見て、どのように流れたかを調べられる。

コード

void solve(int n, int m, vi<string>& s) {
    FF ff(n * m + 2);
    const int dx[4] = { 1, 0, -1, 0 };
    const int dy[4] = { 0, 1, 0, -1 };
    auto tohash = [&](int x, int y) { return m * x + y; };
    rep(i, n) rep(j, m) {
        if (s[i][j] == '#') continue;
        if ((i + j) & 1) {
            ff.addedge(tohash(i, j), n * m + 1, 1);
            continue;
        }
        else ff.addedge(n * m, tohash(i, j), 1);

        rep(k, 4) {
            int ni = i + dx[k], nj = j + dy[k];
            if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
            if (s[ni][nj] == '#') continue;
            ff.addedge(tohash(i, j), tohash(ni, nj), 1);
        }
    }

    int temp = ff.maxflow(n * m, n * m + 1);
    cout << temp << endl;
    rep(i, n) rep(j, m) {
        if (s[i][j] != '.') continue;
        if ((i + j) & 1) {
            rep(k, 4) {
                if (s[i][j] != '.') break;
                int ni = i + dx[k], nj = j + dy[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= m) continue;
                if (s[ni][nj] != '.') continue;
                for (auto nv : ff.to[tohash(i, j)]) {
                    if (nv.to != tohash(ni, nj)) continue;
                    if (nv.cap == 1) {
                        if (k == 0) s[ni][nj] = '^', s[i][j] = 'v';
                        else if (k == 1) s[ni][nj] = '<', s[i][j] = '>';
                        else if (k == 2) s[ni][nj] = 'v', s[i][j] = '^';
                        else if (k == 3) s[ni][nj] = '>', s[i][j] = '<';
                    }
                    break;
                }
            }
        }
    }

    rep(i, n) cout << s[i] << endl;
}

int main()
{
    int n, m;
    cin >> n >> m;
    vi<string> s(n);
    rep(i, n) cin >> s[i];
    solve(n, m, s);
    return 0;
}

SoundHound Inc. Programming Contest 2018 (春) C 広告

市松模様の二部グラフにする典型テクを使う。隣接マス同士で辺を張ると最大安定集合を求める問題に帰着する。二部グラフでは最大安定集合の数は最小辺被覆の数に等しい。

コード


int main()
{
    int r, c;
    cin >> r >> c;

    vi<string> s(r);
    rep(i, r) cin >> s[i];

    Dinic mf(r * c + 2);
    int S = r * c, T = S + 1;

    int dx[] = { 1, 0, -1, 0 };
    int dy[] = { 0, 1, 0, -1 };
    auto f = [&](int i, int j) {
        return c * i + j;
    };
    int cnt = 0;
    rep(i, r) rep(j, c) {
        if (s[i][j] == '*') continue;
        cnt++;
        if ((i + j) & 1) {
            mf.addedge(S, f(i, j), 1);
            rep(k, 4) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                if (ni < 0 || ni >= r || nj < 0 || nj >= c || s[ni][nj] == '*') continue;
                mf.addedge(f(i, j), f(ni, nj), 1);
            }
        }
        else mf.addedge(f(i, j), T, 1);
    }

    cnt -= mf.maxflow(S, T);
    cout << cnt << endl;
    return 0;
}

類題

UnKoder #07 Grid Coloring
ICPC2007 冬合宿 G Oil Company

天下一プログラマーコンテスト2015予選A C 天下一美術館

市松模様の二部グラフにする典型テクを使う。AとBで異なるマス$(i, j)$に対し、上下左右に同じくAとBで異なるマス$(ni, nj)$があったときに辺を張る(マス$(i, j)$とマス$(ni, nj)$は異なる色である条件もあることに注意)。AとBで異なるマスの数をカウントしておき、最大フローを引いた値が答え。

コード

int main()
{
    int m, n;
    cin >> m >> n;

    vii<int> a(m, vi<int>(n));
    vii<int> b(m, vi<int>(n));
    
    rep(i, m) rep(j, n) cin >> a[i][j];
    rep(i, m) rep(j, n) cin >> b[i][j];

    Dinic mf(m * n + 2);
    int S = m * n, T = S + 1;

    int dx[] = { 1, 0, -1, 0 };
    int dy[] = { 0, 1, 0, -1 };
    auto f = [&](int i, int j) {
        return n * i + j;
    };
    int cnt = 0;
    rep(i, m) rep(j, n) {
        if (a[i][j] == b[i][j]) continue;
        cnt++;
        if ((i + j) & 1) {
            mf.addedge(S, f(i, j), 1);
            rep(k, 4) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                if (ni < 0 || ni >= m || nj < 0 || nj >= n 
                    || a[ni][nj] == b[ni][nj] || a[i][j] == a[ni][nj]) continue;
                mf.addedge(f(i, j), f(ni, nj), 1);
            }
        }
        else mf.addedge(f(i, j), T, 1);
    }

    cnt -= mf.maxflow(S, T);
    cout << cnt << endl;
    return 0;
}

ICPC2006 夏合宿 G Make Friendships

　左側にアイザックの(座圧後の)スケジュール、右側に友達をノードとして二部グラフを作成し、フローを流す。$M$の大きさがわからない、スケジュールの時間の範囲がわからないが、intの範囲に収まると祈る。

問題文訳

アイザックは国際学生パーティーに参加し、多くの女性の友達を作りました。彼はこれらの友達と良い関係を築くためにデートを計画しましたが、友達が多すぎてスケジュールを調整するのが難しくなりました。最も重要な基準は、どれだけ多くの異なる友達とデートできるかです。デートできる友達が多いほど良いスケジュールです。

入力
入力は一連のデータセットから成ります。各データセットの最初の行には、パーティーでアイザックが友達になった人数を表す正の整数$N（N \leq 1,000）$が含まれます。次の行にはアイザックのスケジュールが続き、それに続く$N$行には新しい友達のスケジュールが記されています。各スケジュールは、利用可能な日数を表す正の整数$M$と、その$M$個の利用可能な日を表す正の整数から成ります。入力は単一のゼロを含む行で終了します。これはデータセットの一部ではなく、処理しないでください。
出力
各データセットに対して、アイザックがデートできる最大の友達の人数を1行で出力してください。

コード

int main()
{    
    int n;
    while (cin >> n, n) {
        int m;
        cin >> m;
        map<int, int> mp;
        rep(i, m) {
            int x;
            cin >> x;
            mp[x];
        }
        int idx = 0;
        for (auto& elem : mp) elem.second = idx++;

        Dinic dn(m + n + 2);
        int S = m + n, T = m + n + 1;
        rep(i, m) dn.addedge(S, i, 1);
        rep(i, n) dn.addedge(i + m, T, 1);

        rep(i, n) {
            int mg = 0;
            cin >> mg;
            rep(j, mg) {
                int x;
                cin >> x;
                if (mp.count(x)) dn.addedge(mp[x], i + m, 1);
            }
        }

        int flow = dn.maxflow(S, T);
        cout << flow << endl;
    }

    return 0;
}

ICPC2006 冬合宿 D Flame of Nucleus

　WFで都市間の距離を求めておく。左側に市民が元居た都市、右側に市民が避難する先の都市をノードとして二部グラフを作成し、距離が$L$以下の都市間でノードをつなぐ。最大流が答え。
二部グラフではなく、都市を表すノードを一つだけにした(元居た都市と避難先の都市をindexが同じときに一つとした)とき解が合わなかった。理由がよくわかっていないので有識者の方に教えていただきたい。

問題文訳

　　核爆発による放射線汚染が迫る都市で、市民が避難できる最大人数を求める。ドームとパイプラインの構成、市民の数、シェルターの収容能力が与えられ、避難時間内にできるだけ多くの市民をシェルターに避難させる最適な方法を計算せよ。

コード


int main()
{
    ll inf = 1e15;
    int n, m, l;
    vi<ll> ans;
    while (cin >> n >> m >> l) {
        Dinic dn(n * 2 + 2);
        int S = n * 2, T = S + 1;

        vii<ll> dist(n, vi<ll>(n, inf));
        rep(i, n) dist[i][i] = 0;

        rep(i, m) {
            int a, b, d;
            cin >> a >> b >> d;
            a--, b--;
            dist[a][b] = d;
            dist[b][a] = d;
        }

        rep(k, n) rep(i, n) rep(j, n) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

        rep(i, n) rep(j, n) {
            if (dist[i][j] < l) dn.addedge(i, j + n, inf);
        }

        rep(i, n) {
            int p;
            cin >> p;
            dn.addedge(S, i, p);
        }
        rep(i, n) {
            int k;
            cin >> k;
            dn.addedge(i + n, T, k);
        }
        
        ll flow = dn.maxflow(S, T);
        ans.push_back(flow);
        if (cin.eof()) break;
    }
    for (auto elem : ans) cout << elem << endl;
    return 0;
}

ICPC2007 夏合宿 D Private Teacher

　左側に生徒、右側に曜日の二部グラフを作成する。始点から生徒のノードへは必要週数、曜日から終点へは残り週数の容量の辺を張り、フローを流す。

問題文訳

　　あなたは家庭教師として働いており、多くの生徒に授業を行っている。各生徒にとって都合の良い曜日と、必要な授業数が分かっている。1日に1人の生徒に対してのみ授業を行うことができる。試験までに残りの週数が限られている中で、全ての授業を終えられるかを判断してください。

コード

int main()
{
    map<string, int> mp;
    mp["Monday"]    = 0;
    mp["Tuesday"]   = 1;
    mp["Wednesday"] = 2;
    mp["Thursday"]  = 3;
    mp["Friday"]    = 4;
    mp["Saturday"]  = 5;
    mp["Sunday"]    = 6;

    const ll inf = 1e18;

    int n;
    ll w;
    while (cin >> n >> w, n) {
        Dinic dn(n + 9);
        int S = n + 7, T = S + 1;
        ll cnt = 0;
        rep(i, n) {
            ll t;
            int c;
            cin >> t >> c;
            cnt += t;

            dn.addedge(S, i, t);
            rep(j, c) {
                string s;
                cin >> s;
                dn.addedge(i, n + mp[s], inf);
            }
        }

        rep(i, 7) dn.addedge(n + i, T, w);

        ll flow = dn.maxflow(S, T);
        cout << (flow == cnt ? "Yes" : "No") << endl;
    }
    
}

ICPC2009 夏合宿 D Luigi's Tavern

戦士、ヒーラー、魔法使いを使わないの時の特殊頂点をそれぞれ準備する。あとは関係があるノードを結んで最大流を流す。

コード


int main()
{
    vi<int> ans;
    int h, w, c, m, nw, nc, nm;
    while (cin >> h >> w >> c >> m >> nw >> nc >> nm, h >= 0) {
        Dinic dn(h + w + w + c + c + m + 7);
        int S = h + w + w + c + c + m;
        int T = S + 1;
        int WI = S + 2;
        int WO = S + 3;
        int CI = S + 4;
        int CO = S + 5;
        int MI = S + 6;

        rep(i, h) dn.addedge(S, i, 1);

        rep(i, w) {
            int n;
            cin >> n;
            rep(j, n) {
                int idx;
                cin >> idx;
                idx--;
                dn.addedge(idx, i + h, 1);
            }
            dn.addedge(i + h, i + h + w, 1);
        }
        rep(i, h) dn.addedge(i, WI, 1);
        dn.addedge(WI, WO, nw);
        

        rep(i, c) {
            int n;
            cin >> n;
            rep(j, n) {
                int idx;
                cin >> idx;
                idx--;
                dn.addedge(idx + h + w, i + h + w + w, 1);
            }
            dn.addedge(i + h + w + w, i + h + w + w + c, 1);
            dn.addedge(WO, i + h + w + w, 1);
        }
        rep(i, w) dn.addedge(i + h + w, CI, 1);
        dn.addedge(CI, CO, nc);


        rep(i, m) {
            int n;
            cin >> n;
            rep(j, n) {
                int idx;
                cin >> idx;
                idx--;
                dn.addedge(idx + h + w + w + c, i + h + w + w + c + c, 1);
            }
            dn.addedge(i + h + w + w + c + c, T, 1);
            dn.addedge(CO, i + h + w + w + c + c, 1);
        }
        rep(i, c) dn.addedge(i + h + w + w + c, MI, 1);
        dn.addedge(MI, T, nm);

        int flow = dn.maxflow(S, T);
        ans.push_back(flow);
    }
    for (int elem : ans) cout << elem << endl;
    return 0;
}

Indeedなう F 就職活動

S社だけ、N社だけ、K社だけ、S社とK社、K社とN社、N社とS社、全社を希望する人数を $x_s, x_n, x_k, x_{sk}, x_{kn}, x_{sn}, x_{snk}$ としたときに、各組合せにHallの結婚定理を適用する。この条件を満たすときに全員が希望する会社に就職できるようなマッチングが存在する。前計算で $O(X^3)$ で $x_{kn}, x_{sn}, x_{snk}$ の組合せの数を数えておく。残りの $x_s, x_n, x_k, x_{sk}$ の場合の数を $O(X^4)$ で求める。コーナーケース($S+N+K < X$)に注意。

コード

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)

template<class T>
using vi = vector<T>;

template<class T>
using vii = vector<vi<T>>;

template<class T>
using viii = vector<vii<T>>;


struct mint {
    const long long mod = 1e9 + 7; //998244353;
    long long x;
    mint(long long x_ = 0) : x((x_% mod + mod) % mod) {}

    mint& operator+=(const mint& other) {
        x += other.x;
        if (x >= mod) x -= mod;
        return *this;
    }
    mint& operator-=(const mint& other) {
        x -= other.x;
        if (x < 0) x += mod;
        return *this;
    }
    mint& operator*=(const mint& other) {
        x *= other.x;
        x %= mod;
        return *this;
    }

    mint& operator+=(const long long n) {
        return *this += mint(n);
    }
    mint& operator-=(const long long n) {
        return *this -= mint(n);
    }
    mint& operator*=(const long long n) {
        return *this *= mint(n);
    }

    mint& operator=(const mint& other) {
        x = other.x;
        return *this;
    }
    mint& operator=(const long long n) {
        x = n % mod;
        return *this;
    }

    bool operator==(const mint& other) const {
        return x == other.x;
    }
    bool operator!=(const mint& other) const {
        return x != other.x;
    }

    mint operator-() const {
        mint res(mod - x);
        return res;
    }

    mint operator+(const mint& other) const {
        mint res(x);
        return res += other;
    }
    mint operator-(const mint& other) const {
        mint res(x);
        return res -= other;
    }
    mint operator*(const mint& other) const {
        mint res(x);
        return res *= other;
    }

    mint operator+(const long long n) const {
        mint res(x);
        mint other(n);
        return res += other;
    }
    mint operator-(const long long n) const {
        mint res(x);
        mint other(n);
        return res -= other;
    }
    mint operator*(const long long n) const {
        mint res(x);
        mint other(n);
        return res *= other;
    }

    mint pow(long long n) const {
        if (n == 0) return mint(1);
        mint res = pow(n / 2);
        res *= res;
        if (n % 2) res *= *this;
        return res;
    }
    mint inv() const {
        return pow(mod - 2);
    }
    mint& operator/=(const mint& other) {
        *this *= other.inv();
        return *this;
    }
    mint operator/(const mint& other) const {
        mint res(x);
        return res /= other;
    }
};

struct combination {
    vector<mint> fact, ifact;
    combination(int m) :fact(m + 1), ifact(m + 1) {
        fact[0] = 1;
        for (int i = 1; i <= m; i++) fact[i] = fact[i - 1] * mint(i);
        ifact[m] = fact[m].inv();
        for (int i = m; i >= 1; i--) ifact[i - 1] = ifact[i] * mint(i);
    }
    mint operator()(int n, int k) {//for n<=m, calc nck
        if (k < 0 || k > n) return mint(0);
        return fact[n] * ifact[k] * ifact[n - k];
    }
};


int main()
{
    int x, s, n, k;
    cin >> x >> s >> n >> k;
    if(s + n + k < x){
      cout << 0 << endl;
      return 0;
    }

    combination comb(x + 10);
    viii<mint> dp(x + 1, vii<mint>(x + 1, vi<mint>(x + 1)));
    dp[0][0][0] = 1;
    for (int xsk = 0; xsk <= min(x, s + k); xsk++) {
        for (int xnk = 0; xnk <= min(x, n + k); xnk++) {
            for (int rem = xsk + xnk; rem <= x; rem++) {
                dp[xsk][xnk][rem] = comb(rem, xsk) * comb(rem - xsk, xnk);   
            }
        }
    }

    for (int rem = 0; rem <= x; rem++) {
        for (int xsk = 0; xsk <= min(rem, s + k); xsk++) {
            for (int xnk = 1; xnk <= min(rem, n + k); xnk++) {
                dp[xsk][xnk][rem] += dp[xsk][xnk - 1][rem];
            }
        }

        for (int xnk = 0; xnk <= min(rem, n + k); xnk++) {
            for(int xsk = 1; xsk <= min(rem, s + k); xsk++){
                dp[xsk][xnk][rem] += dp[xsk - 1][xnk][rem];
            }
        }
    }



    mint ans = 0;
    for (int xs = 0; xs <= s; xs++) {
        for (int xn = 0; xn <= n; xn++) {
            for (int xk = 0; xk <= k; xk++) {
                for (int xsn = 0; xsn <= max(0, min(x - xs - xn - xk, n + s - xs - xn)); xsn++) {
                    //xsk, xnk, xsnk
                    int rem = x - xs - xn - xk - xsn;
                    int xsk = max(0, min(rem, s + k - xs - xk));
                    int xnk = max(0, min(rem, n + k - xn - xk));
                    if (rem < 0) continue;

                    ans += dp[xsk][xnk][rem] * comb(x, xs) * comb(x - xs, xn) 
                        * comb(x - xs - xn, xk) * comb(x - xs - xn - xk, xsn);
                }
            }
        }
    }
    cout << ans.x << endl;
    return 0;
}

ARC076F Exhausted?

Hallの結婚定理を用いる。任意の高橋君の部分集合$X$に対して、座れる椅子の集合$\Gamma(X)$を考えたときに、$|X|-|\Gamma(X)|$の最大値が答え。区間加算と全体minが取れるような遅延セグ木を使う。

コード

template<class T>
struct lazysegmenttree {
    int n;
    vector<T> d, lazy;
    vector<bool> check;
    T e;
    const T INF = 1e9;

    lazysegmenttree(int n_ = 1) {
        n = 1;
        e = 0;
        while (n < n_) n <<= 1;
        d.resize(2 * n - 1, 0);
        lazy.resize(2 * n - 1, 0);
        check.resize(2 * n - 1);
        //e = e_;
    }

    T op(T x, T y) { return max(x, y); }

    void eval(int i) {
        if (!check[i]) return;
        d[i] += lazy[i]; 

        //子に伝搬
        if (i < n - 1) {
            lazy[2 * i + 1] += lazy[i]; 
            lazy[2 * i + 2] += lazy[i]; 
            check[2 * i + 1] = true;
            check[2 * i + 2] = true;
        }

        lazy[i] = e;
        check[i] = false;
    }

    void update(int l, int r, T x) { return update(l, r, x, 0, 0, n); }

    void update(int l, int r, T x, int i, int ok, int ng) {
        eval(i);
        if (l <= ok && ng <= r) {
            lazy[i] += x; 
            check[i] = true;
            eval(i); 
            return;
        }
        if (r <= ok || ng <= l) return;
        int mid = (ok + ng) / 2;
        update(l, r, x, 2 * i + 1, ok, mid);
        update(l, r, x, 2 * i + 2, mid, ng);
        d[i] = op(d[2 * i + 1], d[2 * i + 2]);
        return;
    }

    T get(int l, int r) { return get_sub(l, r, 0, 0, n); }

    T get_sub(int l, int r, int i, int ok, int ng) {
        eval(i);
        if (l <= ok && ng <= r) return d[i];
        if (r <= ok || ng <= l) return -INF;
        int mid = (ok + ng) / 2;
        T vl = get_sub(l, r, 2 * i + 1, ok, mid);
        T vr = get_sub(l, r, 2 * i + 2, mid, ng);
        return op(vl, vr); 
    }
};

using pii = pair<int, int>;

void chmax(int& x, int y) { x = max(x, y); }

int main()
{
    int n, m;
    cin >> n >> m;
    vi<pii> d(n);
    rep(i, n) {
        int l, r;
        cin >> l >> r;
        d[i] = { l, r };
    }

    sort(d.begin(), d.end());
    int ans = max(0, n - m);

    lazysegmenttree<int> seg(m + 2);
    rep(i, m + 2) 
        seg.update(i, i + 1, -m - 1 + i);
        
    rep(i, n) {
        auto [l, r] = d[i];
        seg.update(0, r + 1, 1);
        int temp = seg.get(l + 1, m + 2);
        chmax(ans, - l + temp);
    }
    cout << ans << endl;
    return 0;
}

ARC080F Prime Flip

　まずは隣同士で裏表が一致するときは$0$、一致しないときは$1$として配列を変換しなおし、区間全体のフリップを区間の両端のフリップに変換する典型テクを用いる。区間の端(値が$1$)として考えられる数は高々$200$個。
端点同士の差が偶数のときはGoldbach予想と$5-3=2, 7-3=4$であることから、$2$回の操作で$0$にできる。奇数の時は、素数の場合は $1$回、非素数の場合は $3$ 回の操作で $0$ にできる。端点の値が偶数か奇数で二部グラフを作り、その最大マッチングとマッチングしなかった残りを考えることにより、答えを得る。

コード

int main()
{
    int n;
    cin >> n;
    vi<int> x(n);
    rep(i, n) cin >> x[i];

    const int mx = 1e7 + 10;
    vi<bool> prime(mx);
    for (ll i = 2; i < mx; i++) {
        if (prime[i]) continue;
        for (ll j = i * i; j < mx; j += i) prime[j] = true;
    }
    prime[0] = prime[1] = prime[2] = true;

    set<int> st;
    vi<int> y;
    rep(i, n) {
        if (!y.empty() && y.back() == x[i]) y.pop_back();
        else y.push_back(x[i]);
        y.push_back(x[i] + 1);
    }

    int sz = (int)y.size();
    Dinic mf(sz + 2);
    int S = sz, T = S + 1;

    int odd = 0, even = 0;
    for(int i = 0; i < sz; i++) {
        if (y[i] & 1) {
            mf.addedge(S, i, 1);
            odd++;
        }
        else {
            mf.addedge(i, T, 1);
            even++;
        }

        for (int j = i + 1; j < sz; j++) {
            int dif = y[j] - y[i];
            if (prime[dif]) continue;
            if (y[i] & 1) mf.addedge(i, j, 1);
            else mf.addedge(j, i, 1);
        }
    }

    int res = mf.maxflow(S, T);

    odd -= res;
    even -= res;
        
    res += odd / 2 * 2 + even / 2 * 2;
    if (odd & 1) res += 3;

    cout << res << endl;
    return 0;
}

yukicoder No.421 しろくろチョコレート

最初から市松模様になっている。隣接するマス同士が空でないとき、wからbへ容量1の辺を張り、1x2の長方形をどれだけとれるかを最大マッチングで求める。端の処理がPrime Flipと似ている。

コード

int main()
{
    int n, m;
    cin >> n >> m;
    vi<string> s(n);
    rep(i, n) cin >> s[i];

    int dx[] = { 1, 0, -1, 0 };
    int dy[] = { 0, 1, 0, -1 };

    auto f = [&](int i, int j) {
        return m * i + j;
    };

    Dinic dn(n * m + 2);
    int S = n * m, T = S + 1;
    int cw = 0, cb = 0;
    rep(i, n) rep(j, m) {
        if (s[i][j] == '.') continue;
        if ((i + j) & 1) {
            dn.addedge(f(i, j), T, 1);
            cb++;
        }
        else {
            dn.addedge(S, f(i, j), 1);
            cw++;
            rep(k, 4) {
                int ni = i + dx[k];
                int nj = j + dy[k];
                if (ni < 0 || ni >= n || nj < 0 || nj >= m || s[ni][nj] == '.') continue;
                dn.addedge(f(i, j), f(ni, nj), 1);
            }
        }
    }

    ll mf = dn.maxflow(S, T);
    cw -= mf, cb -= mf;
    ll res = mf * 100 + min(cw, cb) * 10 + cw + cb - 2 * min(cw, cb);
    cout << res << endl;

    return 0;
}

ABC354G Select Strings

　推移率を満たす半順序集合$(P, \preceq)$において、($P$の最小パス被覆のサイズ)=($P$の最大独立集合のサイズ)が成り立つ、というDilworthの定理を用いる。今回の問題では$S_i$が$S_j$の部分文字列の時に$i \rightarrow j$の有効辺があるようなDAG $G$ に対し、最小パス被覆のサイズが最大独立集合のサイズになることを考える。特に「$N$ 個の頂点 $1,2,…,N$ をもつDAG $G$ を、$N$ 個の左側頂点 $1,2,…,N$ と $N$ 個の右側頂点 $1^′,2^′,…,N^′$ をもつ二部グラフ $H$ に対応」させたとき、($G$ の最小パス被覆のサイズ)=$N$−($H$ の最大マッチングのサイズ)となることを利用する。
　始点$S$から$i$へ$a_i$、$i$から$j$へinf、$j$から終点$T$へ$a_j$の辺を張り、二部グラフの最大独立集合(=最大マッチング)を求め、$\sum{a_i}$からその値を引けば答え。

コード

bool is_substring(const string& a, const string& b) {
    return b.find(a) != string::npos;
}

int main()
{
    int n;
    cin >> n;
    vi<string> s(n);
    rep(i, n) cin >> s[i];
    vi<ll> a(n);
    rep(i, n) cin >> a[i];

    Dinic dn(2 * n + 2);
    int S = 2 * n, T = S + 1;
    
    rep(i, n) {
        dn.addedge(S, i, a[i]);
        dn.addedge(i + n, T, a[i]);
    }

    const ll inf = 1e18;
    rep(i, n) rep(j, n) {
        if (i == j) continue;
        if (!is_substring(s[i], s[j])) continue;
        if (s[i] == s[j]) {
            if (i < j) dn.addedge(i, j + n, inf);
        }
        else dn.addedge(i, j + n, inf);
    }

    ll ans = accumulate(a.begin(), a.end(), 0LL);
    ans -= dn.maxflow(S, T);
    cout << ans << endl;
    return 0;
}

ABC237Ex Hakata

　前問と同じく、Dilworthの定理を用いる。回文となるものを重複を除き、列挙する。二つの回文を取り出し、部分文字列になっているときに有効辺を張る。

コード

int main()
{
    string s;
    cin >> s;
    int n = (int)s.size();

    set<string> d;
    rep(i, n) {
        int l = i, r = i;
        while (l >= 0 && r < n && s[l] == s[r]) {
            d.insert(s.substr(l, r - l + 1));
            l--;
            r++;
        }
        l = i, r = i + 1;
        while (l >= 0 && r < n && s[l] == s[r]) {
            d.insert(s.substr(l, r - l + 1));
            l--;
            r++;
        }
    }

    int sz = (int)d.size();
    Dinic dn(2 * sz + 2);
    int S = 2 * sz, T = S + 1;
    rep(i, sz) dn.addedge(S, i, 1);
    rep(i, sz) dn.addedge(i + sz, T, 1);
        
    {
        int ci = 0, cj = 0;
        for (auto itri = d.begin(); itri != d.end(); itri++) {
            cj = 0;
            for (auto itrj = d.begin(); itrj != d.end(); itrj++) {
                if (ci == cj || !is_substring(*itri, *itrj)) cj++;
                else {
                    dn.addedge(ci, cj + sz, 1);
                    cj++;
                }
            }
            ci++;
        }
    }


    ll mf = dn.maxflow(S, T);
    cout << sz - mf << endl;
    
    return 0;
}

UAPC2014G Yu-kun Likes Building Block

　Dilworthの定理を使う。上における積み木に対して辺を張った時、DAGになる。最小パス被覆のサイズが答え。

コード

int main()
{
    int n;
    cin >> n;
    vi<int> w(n), h(n);
    rep(i, n) cin >> w[i] >> h[i];

    Dinic dn(2 * n + 2);
    int S = 2 * n, T = S + 1;

    rep(i, n) rep(j, n) {
        if (i == j) continue;
        if ((w[i] < w[j] && h[i] < h[j]) || 
            (w[i] < h[j] && h[i] < w[j]))
        {
            dn.addedge(i, j + n, 1);
        }
    }
    rep(i, n) dn.addedge(S, i, 1);
    rep(i, n) dn.addedge(i + n, T, 1);

    int match = dn.maxflow(S, T);
    cout << n - match << endl;
    return 0;
}

ICPC2010 模擬地区予選 J Merry Christmas

　Warshall-Floydで各地点間の距離を$O(N^3)$で求めておく。間に合う都市間に有効辺を張ると推移率をみたすDAGになる。最小パス被覆のサイズが答え。

コード

struct edge {
    int to, cost;
};

int main()
{
    vi<int> ans;
    const int inf = 1e9;
    int n, m, l;
    while (cin >> n >> m >> l, n) {
        vii<int> dist(n, vi<int>(n, inf));
        rep(i, n) dist[i][i] = 0;
        rep(i, m) {
            int u, v, d;
            cin >> u >> v >> d;
            dist[u][v] = d;
            dist[v][u] = d;
        }

        rep(k, n) rep(i, n) rep(j, n) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

        vi<int> p(l), t(l);
        rep(i, l) cin >> p[i] >> t[i];

        Dinic dn(2 * l + 2);
        int S = 2 * l, T = S + 1;

        rep(i, l) dn.addedge(S, i, 1);
        rep(j, l) dn.addedge(j + l, T, 1);

        rep(i, l) {
            rep(j, l) {
                if (i == j) continue;
                if (dist[p[i]][p[j]] == inf) continue;
                if (t[i] + dist[p[i]][p[j]] > t[j]) continue;
                dn.addedge(i, j + l, 1);
            }
        }

        int flow = dn.maxflow(S, T);
        ans.push_back(l - flow);
    }

    for (int elem : ans) cout << elem << endl;
    return 0;
}

Maximum-Cup 2018H Maxmin Tour

　Warshall-Floydで各地点間の距離を$O(N^3)$で求めておく。マッチングの問題に帰着する。左側の点に $a_1, a_2\cdots, a_{K-1}$, 右側の点に $a_2, a_3, \cdots, a_K, b_1, \cdots, b_Q$ を対応させる。$a_i a_{i+1}$ 間は$\mathrm{dist}(a_i, a_{i+1})$, $a_i b_{j}$ 間は$\mathrm{dist}(a_{i+1}, b_j)$以上の値の時に容量1の辺が張られるようにする。$K-1$ 個の最大マッチングができるような最小の距離を求めればよい。最大値の最小値なので二分探索が使えるが、グラフを毎回構築するのを嫌い、小さい順に辺を追加していき、その都度追加でフローを流していく方針とした。他の方の回答を見ると二分探索のほうが速いらしい。

コード

void chmin(ll& x, ll y) { x = min(x, y); }

using ti = tuple<ll, int, int>;

int main()
{
    int n, m;
    cin >> n >> m;

    const ll inf = 1e18 + 10;
    vii<ll> to(n, vi<ll>(n, inf));
    rep(i, n) to[i][i] = 0;
    rep(i, m) {
        int u, v; ll w;
        cin >> u >> v >> w;
        u--, v--;
        to[u][v] = w;
        to[v][u] = w;
    }

    rep(k, n) rep(i, n) rep(j, n) chmin(to[i][j], to[i][k] + to[k][j]);

    int K;
    cin >> K;
    vi<int> a(K);
    rep(i, K) cin >> a[i];
    rep(i, K) a[i]--;

    int Q;
    cin >> Q;
    vi<int> b(Q);
    rep(i, Q) cin >> b[i];
    rep(i, Q) b[i]--;

    vi<ti> vec;
    rep(i, K - 1) rep(j, Q) {
        vec.push_back({ to[a[i + 1]][b[j]], i, 2 * (K - 1) + j}); 
    }

    rep(i, K - 1) vec.push_back({ to[a[i]][a[i + 1]], i, i + K - 1 });

    sort(vec.begin(), vec.end());

    Dinic dn(2 * K + Q);
    int S = 2 * K + Q - 2, T = S + 1;

    rep(i, K - 1) dn.addedge(S, i, 1);
    rep(i, Q + K - 1) dn.addedge(i + K - 1, T, 1);

    ll mf = 0;
    for (auto &elem : vec) {
        auto [dist, l, r] = elem;
        dn.addedge(l, r, 1);
        mf += dn.maxflow(S, T);
        if (mf == K - 1) {
            cout << dist << endl;
            return 0;
        }
    }


    return 0;
}

ICPC2009 夏合宿 G Defend the Bases

　前問同様、所要時間で二分探索して、辺を張るか張らないかを決めて二部グラフを作成する。

コード

#include <camth>
#include <iomanip>

int main()
{
    vi<double> ans;
    int n, m;
    while (cin >> n >> m, n) {
        vi<double> x(n), y(n), v(n);
        vi<double> bx(m), by(m);
        rep(i, n) cin >> x[i] >> y[i] >> v[i];
        rep(j, m) cin >> bx[j] >> by[j];
        
        auto dist = [&](int i, int j) {
            return sqrt((x[i] - bx[j]) * (x[i] - bx[j]) + (y[i] - by[j]) * (y[i] - by[j])) / v[i];
        };

        double ok = 1e6, ng = -1e-10;
        while (abs(ok - ng) > 1e-8) {
            double mid = (ok + ng) / 2;
            Dinic dn(n + m + 2);
            int S = n + m, T = n + m + 1;
            rep(i, n) dn.addedge(S, i, 1);
            rep(j, m) dn.addedge(j + n, T, 1);


            rep(i, n) rep(j, m) {
                if (dist(i, j) <= mid) dn.addedge(i, j + n, 1);
            }

            int flow = dn.maxflow(S, T);
            if (flow == m) ok = mid;
            else ng = mid;
        }
        ans.push_back(ok);        
    }

    for(auto elem : ans) cout << fixed << setprecision(12) << elem << endl;
    return 0;
}

ARC013D 切り分けできるかな？

　各鉄塊に対して高々60通りの分銅が存在し、全鉄塊を考えると高々6000通り。考えられる分銅の種類を左側、右側の頂点として持つグラフを考える。撤回を切った時の分銅のペアとなるものを辺で結ぶ。辺1本が鉄塊1個に相当する。この二部グラフの最小辺被覆を求めればよい。

コード

int main()
{
    int n;
    cin >> n;
    vi<int> x(n), y(n), z(n);
    rep(i, n) cin >> x[i] >> y[i] >> z[i];

    map<int, int> mp;
    rep(t, n) {
        rep(_, 3) {
            for (int i = 1; i < x[t]; i++) mp[i * y[t] * z[t]];
            swap(x, y);
            swap(y, z);
        }
    }

    int idx = 0;
    for (auto& elem : mp) elem.second = idx++;

    Dinic dn(2 * idx + 2);
    int S = 2 * idx, T = S + 1;

    rep(i, idx) dn.addedge(S, i, 1);
    rep(i, idx) dn.addedge(i + idx, T, 1);

    rep(t, n) {
        int vol = x[t] * y[t] * z[t];
        rep(_, 3) {
            for (int i = 1; i < x[t]; i++) {
                int tv = i * y[t] * z[t];
                dn.addedge(mp[tv], mp[vol - tv] + idx, 1);
                dn.addedge(mp[vol - tv], mp[tv] + idx, 1);
            }
            swap(x, y);
            swap(y, z);
        }
    }

    //二部グラフの最小辺被覆
    cout << 2 * idx - dn.maxflow(S, T) << endl;
    return 0;
}

13th PC Koshien Final あみだくじ

　部品数的にあみだくじのたどり方は左上から右下に行く1通りであり、右から左に戻るような経路をたどることはない。左から$j$本目の縦棒から$j+1$番目の縦棒へ張られている横棒を$j:1 \rightarrow n-1$の順にどの部品を使うか貪欲に決めていく。左から何番目の横棒と何番目の部品を使うかで二部グラフを作り、毎回最大マッチングになるまで部品のインデックスを増やすようにする。

コード

int main()
{    
    int n;
    cin >> n;
    n--;
    vii<int> b(n, vi<int>(n));
    rep(i, n) rep(j, n) cin >> b[i][j];

    vi<int> ans(n);
    int S = 2 * n, T = 2 * n + 1;
    rep(j, n) {
        Dinic dn(2 * n + 2);
        rep(k, j) dn.addedge(k, ans[k] + n, 1);
        for (int k = j + 1; k < n; k++) {
            rep(i, n) if(b[i][k]) dn.addedge(k, i + n, 1);
        }

        rep(k, n) dn.addedge(S, k, 1);
        rep(i, n) dn.addedge(i + n, T, 1);

        int flow = 0;
        rep(i, n) {
            if (b[i][j]) {
                dn.addedge(j, i + n, 1);
                flow += dn.maxflow(S, T);
                if (flow == n) {
                    ans[j] = i;
                    for(int k = i + 1; k < n; k++) b[i][k] = 0;
                    break;
                }
            }
        }

        if (flow != n) {
            cout << "no" << endl;
            return 0;
        }
    }


    cout << "yes" << endl;
    rep(i, n) cout << ans[i] + 1 << endl;
    return 0;
}

16th PC Koshien Final 宝の地図

　イラストロジックのような問題。行と列をそれぞれノードとした二部グラフの典型。各辺がマスに対応する。最大流ですべて流れ切れば可能。毎回ソートして大きいものから貪欲にとっていく方法でも可能。

コード

int main()
{
    int w, h;
    cin >> w >> h;

    vi<int> a(w), b(h);
    rep(i, w) cin >> a[i];
    rep(j, h) cin >> b[j];

    int sa = 0, sb = 0;
    rep(i, w) sa += a[i];
    rep(j, h) sb += b[j];
    if (sa != sb) {
        cout << 0 << endl;
        return 0;
    }

    Dinic dn(w + h + 2);
    int S = w + h, T = S + 1;

    rep(i, w) dn.addedge(S, i, a[i]);
    rep(j, h) dn.addedge(j + w, T, b[j]);
    rep(i, w) rep(j, h) dn.addedge(i, j + w, 1);

    cout << (dn.maxflow(S, T) == sa ? 1 : 0) << endl;
    return 0;
}

17th PC Koshien Final 山へ帰そう

　文字を追加ではなく、一文字削除としたほうが考える量が減る。奇数文字と偶数文字で二部グラフを構成し、始点からは奇数文字のノードに、偶数文字のノードから終点に辺を張る。お互いに山に帰れるペアの時、奇数文字と偶数文字のノード間に辺を張り、最大流を求める。

コード

int main()
{
    int n;
    cin >> n;
    map<string, int> mp;
    rep(i, n) {
        string s;
        cin >> s;
        mp[s];
    }

    int idx = 0;
    for (auto& elem : mp) elem.second = idx++;

    Dinic dn(n + 2);
    int S = n, T = n + 1;

    for (auto &elem : mp) {
        int sz = (int)elem.first.size();
        if (sz & 1) dn.addedge(S, elem.second, 1);
        else dn.addedge(elem.second, T, 1);

        rep(i, sz) {
            string s = elem.first.substr(0, i) + elem.first.substr(i + 1);
            if (mp.count(s)) {
                if (sz & 1) dn.addedge(elem.second, mp[s], 1);
                else dn.addedge(mp[s], elem.second, 1);
            }
        }
    }

    ll flow = dn.maxflow(S, T);
    cout << flow << endl;

    return 0;
}

ICPC2016予選プレゼント交換会

　最小流量制限付最大流問題。$m$個の友達関係に対応するノードを左側、$n$個の人に対応するノードを右側として二部グラフを構成する。ソースから左側のノードへは容量1の辺、左側から右側へは対応する友達関係に対して容量1の辺を張る。右側からシンクヘ$h$の容量の辺を張り、最大流が$m$になるかを確認する。$m$にならなければ$h$を増やしていく。$m$になった段階で、右側のノードからシンクその2に対して$l$の容量の辺を張り、シンクからシンクその2に対して、$lN$の容量だけ押し戻せるか調べる。押し戻せなかった場合は$h$を増やす。尺取りの要領で行うことで、$O(n^7)$で解ける。Dinicの高速化で制限時間内に通る。
　別解は貪欲法。最初に適当にプレゼントを割り振り、プレゼントを渡された人から渡した人へ容量1の辺を張り、ある人から2個以上多いプレゼントを持つ別の人へのパスがある場合、フローを流す操作をひたすら繰り返す。操作できなくなったときの最大値と最小値が答え。深さ優先探索に$O(n+m)$、操作回数が$O(n^2)$なので、全体の計算量は$O(n^2(n+m))$となる。

コード


int main() 
{
    vi<pair<int, int>> ans;
    int n, m;
    while (cin >> n >> m, n) {
        vi<int> u(m), v(m);
        rep(i, m) cin >> u[i] >> v[i];
        rep(i, m) u[i]--;
        rep(i, m) v[i]--;

        int high = n, low = 0;
        int S = n + m, T = S + 1, T2 = S + 2;

        auto f = [&](int h, int l) {
            Dinic dn(n + m + 3);
            rep(i, m) dn.addedge(S, i, 1);
            rep(i, m) {
                dn.addedge(i, m + u[i], 1);
                dn.addedge(i, m + v[i], 1);
            }
            rep(i, n) {
                dn.addedge(m + i, T, h);
                dn.addedge(m + i, T2, l);
            }
            return dn;
        };

        rep(l, n + 1) {
            for(int h = l; h <= min(n, l + high - low); h++) {
                Dinic dn = f(h, l);
                
                int flow = dn.maxflow(S, T);
                if (flow < m) continue;

                int flow_l = dn.maxflow(T, T2);
                if (flow_l < l * n) continue;

                if (h - l <= high - low) {
                    high = h;
                    low = l;
                    break;
                }
            }
        }
        ans.push_back({ low, high });
    }
    for (auto elem : ans) cout << elem.first << " " << elem.second << endl;
	return 0;
}

コード(貪欲)

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)

template<class T>
using vi = vector<T>;

template<class T>
using vii = vector<vi<T>>;

template<class T>
using viii = vector<vii<T>>;

struct edge {
    int to, cap, rev;
};

int main()
{
    vi<pair<int, int>> ans;
    int n, m;
    while (cin >> n >> m, n) {
        vii<edge> to(n);
        vi<int> deg(n);
        rep(i, m) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            int su = (int)to[u].size();
            int sv = (int)to[v].size();
            to[u].push_back({ v, 0, sv });
            to[v].push_back({ u, 1, su });
            deg[u]++;
        }

        vi<bool> visited(n);
        auto dfs = [&](auto dfs, int s, int v)->bool {
            visited[v] = true;
            if (deg[s] + 2 <= deg[v]) {
                deg[v]--;
                deg[s]++;
                return true;
            }
            for (auto& elem : to[v]) {
                if (elem.cap == 0 || visited[elem.to]) continue;
                if (dfs(dfs, s, elem.to)) {
                    elem.cap = 0;
                    to[elem.to][elem.rev].cap = 1;
                    return true;
                }
            }
            return false;
            };

        bool ok = true;
        while (ok) {
            ok = false;
            rep(v, n) {
                visited.assign(n, false);
                ok |= dfs(dfs, v, v);
            }
        }
        sort(deg.begin(), deg.end());
        ans.push_back({ *deg.begin(), *deg.rbegin()});
    }

    for (auto elem : ans) cout << elem.first << " " << elem.second << endl;
    return 0;
}

2.3 燃やす埋める問題

ARC085E MUL

　最初に正の$a_i$をすべて合計しておく。正の$a_i$の宝石については壊したら罰金、負の$a_i$の宝石については壊さなかったら罰金、$j$が$i$の倍数のとき、$i$から$j$へinfの辺を張り、燃やして埋める。最初の合計から最大流(最小カット)の値を引けば答え。

コード

int main()
{
    int n;
    cin >> n;
    ll ans = 0;
    FF ff(n + 2);
    int S = 0, T = n + 1; //S側：壊した、T側：壊さなかった
    const ll inf = 1e18;
    for(int i = 1; i <= n; i++) {
        ll a;
        cin >> a;
        if (a > 0) {
            ans += a;
            ff.addedge(S, i, 0); 
            ff.addedge(i, T, a); 
        }
        else {
            ff.addedge(S, i, -a);
            ff.addedge(i, T, 0);
        }
        for (int j = 2 * i; j <= n; j += i) {
            ff.addedge(i, j, inf);
        }        
    }
    ans -= ff.maxflow(S, T);
    cout << ans << endl;
    return 0;
}

2.4 点素・辺素パス

ACPC2018Day2 I Shiritori

　文字c1で始まり、文字c2で終わるとき、c1からc2へ有効辺を張る。文字cが条件を満たすかを考える。cから出ている辺をすべて使い切り、cに戻ってくればよい。辺連結度の考え方を用いて解く。

コード

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    int n;
    cin >> n;

    vi<string> s(n);
    rep(i, n) cin >> s[i];

    //文字cを頂点とみなし、indeg: cで終わる、outdeg: cで始まる
    int mx = 26;
    vi<int> indeg(mx), outdeg(mx);
    rep(i, n) {
        indeg[s[i].back() - 'a']++;
        outdeg[s[i].front() - 'a']++;
    }

    vi<char> ans;
    rep(i, mx) {
        char c = 'a' + i;

        //cで終わるものがそもそもない
        if (indeg[i] == 0) continue;

        //cから出ていくことはない
        if (outdeg[i] == 0) {
            ans.push_back('a' + i);
            continue;
        }

        //cで始まるのものがcで終わるものより多い
        if (indeg[i] < outdeg[i]) continue;

        Dinic dn(mx + 2);
        int S = mx, T = S + 1;
        
        rep(j, n) {
            char sf = s[j].front();
            char sb = s[j].back();
            int u = sf - 'a';
            int v = sb - 'a';
            if (sf == c) u = S;
            if (sb == c) v = T;
            dn.addedge(u, v, 1);
        }

        int flow = dn.maxflow(S, T);
        if (flow == outdeg[i]) ans.push_back(c);
    }

    for (char c : ans) cout << c << endl;
    return 0;
}

2.5 最小費用流

ALPC E MinCostFlow

　行と列で二部グラフを作る典型。始点から各行のノードに容量$K$、同様に各列のノードから終点へ容量$K$の辺を張る。最大費用を求めたいので、$A_{ij}$は$-1$倍する。負辺を避けるためにすべて一律にコストとしてinfを足す。さらに始点から終点へのコストinf, 容量$n^2$のバイパスを作る。そのうえで容量$N^2$の始点から終点への最小費用流を流す。$N^2 \times\mathrm{inf}$ から最小費用流を引けば答え。

コード

nt main()
{
    int n, k;
    cin >> n >> k;
    vii<ll> a(n, vi<ll>(n));
    rep(i, n) rep(j, n) cin >> a[i][j];

    MCF mcf(2 * n + 2);
    int S = 2 * n, T = 2 * n + 1;
    const ll inf = 1e9 + 10;

    rep(i, n) mcf.addedge(S, i, k, 0);
    rep(j, n) mcf.addedge(j + n, T, k, 0);
    rep(i, n) rep(j, n) mcf.addedge(i, j + n, 1, inf - a[i][j]);
    mcf.addedge(S, T, n * n, inf);

    ll cost = mcf.mincostflow(S, T, n * n);
    cout << inf * n * n - cost << endl;


    vii<char> res(n, vi<char>(n, '.'));
    rep(i, n) {
        for (auto elem : mcf.to[i]) {
            int j = elem.to - n;
            if (j < 0 || j >= n || elem.cap) continue;
            res[i][j] = 'X';
        }
    }
    rep(i, n) {
        rep(j, n) cout << res[i][j];
        cout << endl;
    }
    return 0;
}

11th PC Koshien Final 微生物発電

　重み付き二部グラフの最大マッチングは最小費用流に帰着できる。オスとメスの二部グラフとして考え、発電量をコストとして辺を張る。なお、制約的にbitDPが想定解と思われる。

コード


int main()
{
    vi<int> ans;

    const ll inf = 1e18;
    auto energy = [&](int x, int y) {
        int z = abs(x - y);
        return z * (z - 30) * (z - 30);
    };

    int m, w;
    while (cin >> m >> w, m) {
        vi<int> bm(m), bw(w);
        rep(i, m) cin >> bm[i];
        rep(i, w) cin >> bw[i];
        
        MCF mcf(m + w + 2);
        int S = m + w, T = m + w + 1;

        rep(i, m) mcf.addedge(S, i, 1, 0);
        rep(i, w) mcf.addedge(i + m, T, 1, 0);

        rep(i, m) rep(j, w) {
            mcf.addedge(i, j + m, 1, -energy(bm[i], bw[j]));
        }
        ans.push_back(mcf.mincostflow(S, T, min(m, w)));
    }
   
    for (int elem : ans) cout << -elem << endl;
    return 0;
}

11th PC Koshien Final アルゴリズム検定試験

　会場の組合せは高々$2^M$通りなので、これを全探索する。$F(i+2)-F(i+1) \geq F(i+1)-F(i)$より、$F$は下に凸の関数。使用する会場の個数を$C$としたとき、$D=i$のときのバスの使用料金は$iBC$となる。よって、バスの使用料金と移動補助金の和$G(i)=F(i)+iBC$も$i$に関して下に凸の関数。$i$の候補としてあり得る距離を列挙し、三分探索で絞り込むことで極小値を求める。
　おおよその計算量を見積もる(間違っている可能性あり)。最小費用流としては流れるフロー$F=O(N)$, 辺数$E=O(MN)$, 頂点数$V=O(N+M)$であることから、1回の最小費用流のオーダーは$FE\mathrm{log}V=O(N^2M\mathrm{log}(N+M))$。三分探索に$O(\mathrm{log}(MN))$かかることも踏まえ、1回のテストケースに対して、$O(2^M N^2M\mathrm{log}(N+M)\mathrm{log}(MN))$となる。$M=5, N=100$として、$10^8$程度かかる。

コード

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    vi<ll> res;
    const ll inf = 1e18;
    int n, m, b;
    while (cin >> n >> m >> b, n) {
        vi<ll> ax(n), ay(n), bx(m), by(m), c(m), f(m);
        rep(i, n) cin >> ax[i] >> ay[i];
        rep(i, m) cin >> bx[i] >> by[i] >> c[i] >> f[i];

        ll ans = inf;
        auto dist = [&](int pa, int pb) {
            return abs(ax[pa] - bx[pb]) + abs(ay[pa] - by[pb]);
        };

        

        rep(bit, 1 << m) {
            ll ta = 0;
            int cnt = 0;
            int participants = 0;
            vi<int> dl;
            dl.push_back(0);
            rep(i, m) if(bit >> i & 1) rep(j, n) dl.push_back(dist(j, i));
            sort(dl.begin(), dl.end());
            dl.erase(unique(dl.begin(), dl.end()), dl.end());


            rep(i, m) if (bit >> i & 1) {
                ta += f[i];
                participants += c[i];
                cnt++;
            }
            if (ans <= ta) continue; //暫定解が既に会場使用料より安い
            if (participants < n) continue; //会場人数が受験者より少ない

            ll pf = inf;
            int sz = (int)dl.size();
            int ok = -1, ng = sz;

            auto df = [&](int d) {
                MCF mcf(m + n + 2);
                int S = m + n, T = m + n + 1;

                rep(i, m) if (bit >> i & 1) {
                    mcf.addedge(S, i, c[i], 0);
                    rep(j, n) {
                        mcf.addedge(i, j + m, 1, max(0LL, dist(j, i) - d));
                    }
                }
                rep(j, n) mcf.addedge(j + m, T, 1, 0);
                return mcf.mincostflow(S, T, n) + d * b * cnt;
            };
            
            while (ok + 2 < ng) {
                int lc = (2 * ok + ng) / 3, rc = (ok + 2 * ng) / 3;
                ll fl = df(dl[lc]), fr = df(dl[rc]);
                if (fl < fr) ng = rc;
                else ok = lc;
            }
            ans = min(ans, ta + df(dl[(ok + ng) / 2]));

        }
        res.push_back(ans);
    }
    for (ll elem : res) cout << elem << endl;
    return 0;
}

10th PC Koshien Final 図画工作

　DPでそれぞれの部品をある個数手に入れるのに必要な最小費用を求めておく。各課題と袋を辺でつなぎ、その際の費用をDPで求めた値、容量を1とする。何も入っていない袋を用意し、何もないっていない袋から終点までの容量はn(もしくはinf)としておき、最小費用流を流す。
　「それぞれの課題について、１回の授業でＬ個までの部品を購入することができる。」を「それぞれの授業で」と誤読し、沼にはまった。

コード

void chmin(ll& x, ll y) { x = min(x, y); }

int main()
{
    vi<ll> ans;

    vi<int> pow3(10);
    pow3[0] = 1;
    rep(i, 9) pow3[i + 1] = pow3[i] * 3;
    const ll inf = 1e18;

    //d:授業数、k:部品種類数、l:1日に購入できる数、 m:課題数、n:生徒数、 p:袋数
    int d, k, l, m, n, p;
    while (cin >> d >> k >> l, d) {
        vii<int> c(d, vi<int>(k)); //部品の価格
        rep(i, d) rep(j, k) cin >> c[i][j];

        cin >> m >> n >> p;
        vii<int> r(m, vi<int>(k));
        vii<int> t(p, vi<int>(k));
        rep(i, m) rep(j, k) cin >> r[i][j]; //課題の部品数
        rep(i, p) rep(j, k) cin >> t[i][j]; //袋の部品数
        t.push_back(vi<int>());
        rep(j, k) t[p].push_back(0); //空の袋を入れる

        //dp[x][y][z]: x回目の授業, y:3^k通りで表す部品の状況, z個購入
        viii<ll> dp(d + 1, vii<ll>(pow3[k], vi<ll>(l + 1, inf)));
        dp[0][0][0] = 0;
        rep(x, d) rep(y, pow3[k]){
            if(x) rep(z, l + 1) chmin(dp[x][y][0], dp[x - 1][y][z]);
            rep(z, l) rep(w, k) {
                if ((y / pow3[w]) % 3 == 2) continue;
                chmin(dp[x][y + pow3[w]][z + 1],
                    dp[x][y][z] + c[x][w]);
            }
        }

        rep(y, pow3[k]) rep(z, l + 1) chmin(dp[d][y][0], dp[d - 1][y][z]);

        MCF mcf(m + p + 3);
        int S = m + p + 1, T = m + p + 2;

        rep(i, m) mcf.addedge(S, i, 1, 0);
        rep(i, p) mcf.addedge(i + m, T, 1, 0);
        mcf.addedge(m + p, T, n, 0);

        rep(i, m) rep(j, p + 1) { //i番目の課題, j番目の袋
            int bit = 0;
            bool ok = true;
            rep(h, k) { //h番目の部品
                if (r[i][h] < t[j][h]) { //袋の部品数のほうが多いとき
                    ok = false;
                    break;
                }
                bit += (r[i][h] - t[j][h]) * pow3[h];
            }
            if (!ok) continue;
            if (dp[d][bit][0] != inf) mcf.addedge(i, j + m, 1, dp[d][bit][0]);
        }

        ll cost = mcf.mincostflow(S, T, n);
        ans.push_back(cost);
    }
    for (ll elem : ans) cout << elem << endl;
    return 0;
}

UAPC2012E School Excursion

　同じ駅内の時刻は昇順に辺を張る。時刻は座標圧縮しておく。同時刻に到着する電車は高々1個となるようにin側の頂点とout側の頂点を作り、inからoutへ容量1、コスト0の辺を張る。毎回最小費用流を流し、流せなくなったらそのときのクラス数と費用を出力する。

コード

int main()
{
    int n;
    while (cin >> n, n) {
        vi<int> m(n - 1);
        vii<int> x(n - 1), y(n - 1), c(n - 1);
        int sm = 0;
        rep(i, n - 1) {
            cin >> m[i];
            sm += m[i];
            rep(j, m[i]) {
                int tx, ty, tc;
                cin >> tx >> ty >> tc;
                x[i].push_back(tx);
                y[i].push_back(ty);
                c[i].push_back(tc);
            }
        }
        int g;
        cin >> g;

        MCF mcf(4 * sm + 2);
        int S = 4 * sm, T = S + 1;
        const ll inf = 100; //クラスは最大10個

        map<int, int> mp;
        int idx = 0;
        rep(i, n) {
            mp.clear();
            if (i > 0) rep(j, m[i - 1]) mp[y[i - 1][j]];
            if (i < n - 1) rep(j, m[i]) mp[x[i][j]];

            for (auto& elem : mp) elem.second = idx++;

            set<int> st;
            if (i > 0) rep(j, m[i - 1]) {
                y[i - 1][j] = mp[y[i - 1][j]];
                if (st.count(y[i - 1][j])) continue;
                st.insert(y[i - 1][j]);
                mcf.addedge(y[i - 1][j] + 2 * sm, y[i - 1][j], 1, 0);
            }
            if (i < n - 1) rep(j, m[i]) x[i][j] = mp[x[i][j]];

            auto itr = mp.begin();
            while (next(itr) != mp.end()) {
                mcf.addedge(itr->second, next(itr)->second, inf, 0);
                itr++;
            }
        }

        rep(i, n - 1) {
            set<int> st;
            if (i == 0) rep(j, m[i]) mcf.addedge(S, x[i][j], 1, 0); 
            if (i == n - 2) rep(j, m[i]) mcf.addedge(y[i][j], T, 1, 0);

            //xからy(倍加頂点側)への辺
            rep(j, m[i]) mcf.addedge(x[i][j], y[i][j] + 2 * sm, 1, c[i][j]);
        }

        ll cost = 0;
        for (int flow = 1; flow <= g; flow++) {
            ll tc = mcf.mincostflow(S, T, 1);
            if (tc < 0) {
                cout << flow - 1 << " " << cost << endl;
                break;
            }
            cost += tc;
            if (flow == g) cout << flow << " " << cost << endl; //here?
        }

    }

    return 0;
}

UAPC2012 KND Factory

　掃き出し法で温度を求める。それぞれの都市間に温度差に依存したコストの辺を張り、フローを流す。コストは適当に大きな数で乗算し、最後に割る。浮動小数点演算のほうが速いため、最初から浮動小数点のコストに対応した最小費用流とするのも手。

コード

void inv(int n, vii<double>& a) {
    rep(k, n) {
        double mx = a[k][k];  
        int idx = k;
        for(int i = k + 1; i < n; i++) if (abs(a[i][k]) > mx) {
            idx = i;
            mx = abs(a[i][k]);
        }
        swap(a[k], a[idx]);

        for(int j = n; j >= k; j--) a[k][j] /= a[k][k];

        rep(i, n) {
            if (i == k) continue;
            for (int j = n; j >= k; j--) {
                a[i][j] -= a[i][k] * a[k][j];
            }
        }
    }
}

void solve() {
    int n, s, t, F;
    cin >> n >> s >> t >> F;
    vii<double> a(n, vi<double>(n + 1));
    rep(i, n) rep(j, n + 1) cin >> a[i][j];

    vii<double> b = a;
    inv(n, a);

    MCF mcf(n + 2);
    int S = n, T = n + 1;
    mcf.addedge(S, s, F, 0);
    mcf.addedge(t, T, F, 0);    

    ll mul = 1e10;
    auto diftemp = [&](int i, int j) { return (ll)(abs(a[i][n] - a[j][n]) * mul); };

    rep(i, n) {
        int m;
        cin >> m;
        vi<int> d(m), f(m);
        rep(j, m) cin >> d[j];
        rep(j, m) cin >> f[j];
        rep(j, m) mcf.addedge(i, d[j], f[j], diftemp(i, d[j]));
    }
    double ans = mcf.mincostflow(S, T, F);
    if (ans == -1) cout << "impossible" << endl;
    else cout << fixed << setprecision(12) << (double)ans / mul << endl;
}

int main()
{
    int t;
    cin >> t;    
    while (t--) solve();
    return 0;
}

ICPC2003G Concert Hall Scheduling

　Intervals(蟻本p.220)と似た問題。365日間の各ノードを作り、翌日のノードに向かって容量inf, コスト0の辺を張る。申請[$i, j, w$]に関しては$i$から$j+1$のノードに容量1, コスト$-w$の辺を張る。負辺が存在するので、適当に正にしてあげる必要があるが、今回のテストケースではそのままでも通った。

コード

int main()
{
    int n;
    int S = 0, T = 367;    
    vi<ll> res;
    while (cin >> n, n) {
        MCF mcf(T + 1);
        rep(i, T) mcf.addedge(i, i + 1, 2, 0);
        rep(i, n) {
            int l, r, w;
            cin >> l >> r >> w;
            mcf.addedge(l, r + 1, 1, -w);
        }

        ll ans = -mcf.mincostflow(S, T, 2);
        res.push_back(ans);
    }
    for (ll elem : res) cout << elem << endl;
    return 0;
}

問題文要約

　あなたは有名なコンサートホールの館長として、ホールを破産の危機から救うため、申請者が希望価格を提示する新しい制度を導入しました。コンサートホールには区別できない2部屋があります。各申請は特定の期間と価格を含み、部屋は1日1回しか使用できません。使用期間中は同じ部屋を使い続けます。各申請を全期間受け入れるか完全に拒否するかを選び、年間の総収入を最大化してください。

入力

複数のデータセット
各データセットの最初に申請数 $n$
各申請は [$i, j, w$] の形式で、$i$ は開始日、$j$ は終了日、$w$ は希望価格
単一のゼロの行は入力の終わりを示す

出力

各データセットの最大総収入を1行で出力

UAPC2015 Movie

　各日付と映画の間にコスト0の辺を張る。映画から終点にコスト-100, 容量1の辺とコスト-50, 容量infの辺を張り、最小費用流を求める。本来負辺除去が必要だが、しなくてもテストケースは通る。

コード

int main()
{
    int n;
    cin >> n;

    int mx = 31;
    MCF mcf(mx + n + 2);
    int S = mx + n, T = S + 1;

    rep(i, n) {
        int a, b;
        cin >> a >> b;
        a--;
        for (int j = a; j < b; j++) mcf.addedge(j, i + mx, 1, 0);
    }

    rep(j, mx) mcf.addedge(S, j, 1, 0);
    rep(i, n) {
        mcf.addedge(i + mx, T, 1, -100);
        mcf.addedge(i + mx, T, mx, -50);
    }

    int ans = -mcf.mincostflow(S, T, mx);
    cout << ans << endl;
    return 0;
}

ICPC2007 夏合宿 C Nagashi Soumen

　　$n \leq k$のときは自明に0となる。それ以外の時はDilworthの定理での最小パス被覆と同じ要領で、$z_i > z_j$の時に$i$から$j^\prime$への容量1, コストEuclidean distanceの辺を張る。$n-k$のフローを流した時の最小費用が答え。

コード

#include <cmath>
#include <iomanip>

int main()
{
    vi<double> ans;
    int n, k;
    while (cin >> n >> k, n) {
        vi<int> x(n), y(n), z(n);
        rep(i, n) cin >> x[i] >> y[i] >> z[i];

        if (n <= k) {
            ans.push_back(0);
            continue;
        }
        
        MCF mcf(n * 2 + 2);
        int S = n * 2, T = S + 1;
        double mul = 1e11;

        auto f = [&](int i, int j) {
            double dist = sqrt((x[i] - x[j]) * (x[i] - x[j]) 
                            + (y[i] - y[j]) * (y[i] - y[j])
                            + (z[i] - z[j]) * (z[i] - z[j])) * mul;
            return (ll)dist;
        };
        rep(i, n) rep(j, n) {
            if (z[i] <= z[j]) continue;
            mcf.addedge(i, j + n, 1, f(i, j));
        }
        rep(i, n) mcf.addedge(S, i, 1, 0);
        rep(i, n) mcf.addedge(i + n, T, 1, 0);

        double flow = mcf.mincostflow(S, T, n - k);
        if (flow < 0) ans.push_back(-1);
        else ans.push_back(flow / mul);
    }

    for (auto elem : ans) cout << fixed << setprecision(12) << elem << endl;
    return 0;
}

ICPC2011 夏合宿 A Attack the Moles

手の交差は最適解を求める際に気にしなくてもよい(右手で殴るもぐらと左手で殴るモグラを交換すればいい)。移動できるノードを有効辺で結ぶと推移率を満たすDAGになる。時間順に並べてからBellman-Fordを使うと、$O(1)$回でポテンシャルが求まる。容量2の最小費用流が答え。メモリ制限が厳しいため、flowの型をintに取りなおした。

コード


#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)

template<class T>
using vi = vector<T>;

template<class T>
using vii = vector<vi<T>>;

template<class T>
using viii = vector<vii<T>>;


template<class T>
struct MCF {
private:
    const T inf = 1e9;
    vector<T> dist;       //最短距離(費用)
    vector<int> pv, pe;     //直前の頂点、辺    

public:
    struct edge {
        int to, rev; int cap; T cost;
        edge(int t = 0, int r = 0, int ca = 0, T co = 0)
            : to(t), rev(r), cap(ca), cost(co) {}
    };

    struct pii {
        T d; int v; //最短距離(費用)、頂点番号
        pii(T d_ = 0, int v_ = 0) : d(d_), v(v_) {}

        bool operator<(const pii& other) const {
            if (d != other.d) return d < other.d;
            return v < other.v;
        }

        bool operator>(const pii& other) const {
            if (d != other.d) return d > other.d;
            return v > other.v;
        }
    };

    int n;
    vector<vector<edge>> to;
    vector<T> pot;        //ポテンシャル

    MCF(int n_ = 1) : n(n_), to(n_), pot(n_), dist(n_), pv(n_), pe(n_) {}

    void addedge(int u, int v, int cap, T cost) {
        int su = (int)to[u].size();
        int sv = (int)to[v].size();
        to[u].push_back({ v, sv, cap, cost });
        to[v].push_back({ u, su, 0, -cost });
    }

    bool bellmanford(int s, int t) {
        dist.assign(n, inf);
        dist[s] = 0;
        int cnt = 0;
        while (cnt < n) {
            bool end = true;
            for (int v = 0; v < n; v++) {
                if (dist[v] == inf) continue;
                for (auto e : to[v]) {
                    if (e.cap == 0) continue;
                    if (dist[v] + e.cost < dist[e.to]) {
                        dist[e.to] = dist[v] + e.cost;
                        end = false;
                    }
                }
            }
            cerr << cnt << " ";

            if (end) break;
            cnt++;
        }

        for (int v = 0; v < n; v++) pot[v] += dist[v];

        return (cnt == n);
    }

    //s->tへ流量fの最小費用流、流せないときは-1
    T mincostflow(int s, int t, int f) {
        T res = 0;
        pot.assign(n, 0);
        bellmanford(s, t);
        while (f) {
            priority_queue<pii, vector<pii>, greater<pii>> pq;
            dist.assign(n, inf);
            dist[s] = 0;
            pq.push({ 0, s });
            while (!pq.empty()) {
                pii elem = pq.top();
                pq.pop();
                if (dist[elem.v] < elem.d) continue;
                int sv = (int)to[elem.v].size();
                for (int i = 0; i < sv; i++) {
                    edge& nv = to[elem.v][i];
                    if (nv.cap == 0 || dist[nv.to] + pot[nv.to] <= dist[elem.v] + pot[elem.v] + nv.cost) continue;
                    dist[nv.to] = dist[elem.v] + pot[elem.v] - pot[nv.to] + nv.cost;
                    pv[nv.to] = elem.v;
                    pe[nv.to] = i;
                    pq.push({ dist[nv.to], nv.to });
                }
            }

            if (dist[t] == inf) return -1; //流せる最小費用流が存在しない

            for (int v = 0; v < n; v++) pot[v] += dist[v];

            int nf = f;
            for (int v = t; v != s; v = pv[v]) nf = min(nf, to[pv[v]][pe[v]].cap);
            f -= nf;
            res += nf * (pot[t] - pot[s]); //pot[s] = 0で不要だがポテンシャルを明確化する
            for (int v = t; v != s; v = pv[v]) {
                edge& nv = to[pv[v]][pe[v]];
                nv.cap -= nf;
                to[v][nv.rev].cap += nf;
            }
        }
        return res;
    }

    //s->tへ流量fの最小費用流、流せないときは費用と流せなかった流量のペア
    pair<T, int> mincostflow_pair(int s, int t, int f) {
        T res = 0;
        pot.assign(n, 0);
        while (f) {
            priority_queue<pii, vector<pii>, greater<pii>> pq;
            dist.assign(n, inf);
            dist[s] = 0;
            pq.push({ 0, s });
            while (!pq.empty()) {
                pii elem = pq.top();
                pq.pop();
                if (dist[elem.v] < elem.d) continue;
                int sv = (int)to[elem.v].size();
                for (int i = 0; i < sv; i++) {
                    edge& nv = to[elem.v][i];
                    if (nv.cap == 0 || dist[nv.to] + pot[nv.to] <= dist[elem.v] + pot[elem.v] + nv.cost) continue;
                    dist[nv.to] = dist[elem.v] + pot[elem.v] - pot[nv.to] + nv.cost;
                    pv[nv.to] = elem.v;
                    pe[nv.to] = i;
                    pq.push({ dist[nv.to], nv.to });
                }
            }

            if (dist[t] == inf) return { res, f }; //流せる最小費用流が存在しない

            for (int v = 0; v < n; v++) pot[v] += dist[v];

            long long nf = f;
            for (int v = t; v != s; v = pv[v]) nf = min(nf, to[pv[v]][pe[v]].cap);
            f -= nf;
            res += nf * (pot[t] - pot[s]); //pot[s] = 0で不要だがポテンシャルを明確化する
            for (int v = t; v != s; v = pv[v]) {
                edge& nv = to[pv[v]][pe[v]];
                nv.cap -= nf;
                to[v][nv.rev].cap += nf;
            }
        }
        return { res, f };
    }
};

vi<int> x(3010), t(3010), p(3010);
vi<tuple<int, int, int>> xtp(3010, { 1e9, 1e9, 1e9 });
MCF<int> mcf(6020);

int main()
{
    int n; ll v, xl, xr;
    cin >> n >> v >> xl >> xr;
    rep(i, n) cin >> x[i] >> t[i] >> p[i];
    rep(i, n) xtp[i] = { t[i], x[i], p[i] };
    sort(xtp.begin(), xtp.end());
    rep(i, n) {
        t[i] = get<0>(xtp[i]);
        x[i] = get<1>(xtp[i]);
        p[i] = get<2>(xtp[i]);
    }

    int S = 0, S1 = 1, S2 = 2, T = 2 * n + 3;

    mcf.addedge(S, S1, 1, 0);
    mcf.addedge(S, S2, 1, 0);

    rep(_, 2) {
        rep(i, n) {
            ll dx = abs(x[i] - xl);
            ll dt = t[i];
            if (dx <= dt * v) mcf.addedge(S1, 2 * i + 3, 1, -p[i]);
        }
        swap(xl, xr);
        swap(S1, S2);
    }

    rep(i, n) {
        mcf.addedge(2 * i + 3, 2 * i + 4, 1, 0);
        rep(j, n) {
            if (i == j) continue;
            if (t[i] > t[j]) continue;
            ll dx = abs(x[j] - x[i]);
            ll dt = t[j] - t[i];
            if (dx <= dt * v) mcf.addedge(2 * i + 4, 2 * j + 3, 1, -p[j]);
        }
        mcf.addedge(2 * i + 4, T, 1, 0);
    }

    mcf.addedge(S1, T, 1, 0);
    mcf.addedge(S2, T, 1, 0);

    ll ans = mcf.mincostflow(S, T, 2);
    cout << -ans << endl;

    return 0;
}

3. 最後に

　適宜問題は追加していきたいと思います。間違いはご指摘いただけるとありがたいです。