ShoppingSpree [SRM 770 Div1 Med]

https://community.topcoder.com/stat?c=problem_statement&pm=15702

N種類のシャツがあり、それぞれshirtValue[i]を持つ。
M種類のジーンズがあり、それぞれjeansValue[i]を持つ。
D種類のペアがあり、(i番目のシャツ, j番目のジーンズ)のようにそれぞれ1種類を指す。
K枚クーポンがあり、1枚クーポンを使うと、D種類あるペアのいずれかのパターンでシャツとジーンズを買える。
i番目のシャツが1枚以上買われていればshirtValue[i]点取得する。
j番目のジーンズが1枚以上買われていればjeansValue[i]点取得する。
最適に購入して点数を最大化せよ。

1≦N,M,K,D≦100
1≦shirtValue[i], jeansValue[j]≦10⁶

前提知識

• 最小費用流

解説

マッチングっぽい雰囲気を感じるし、制約もフローっぽいので、そっち方面で考えていると最小費用流で解けると思いつく。
以下のようなフローを構築して、流量Kを流す。

0～N-1 : シャツ頂点
N～N+M-1：ジーンズ頂点
N+M (=st) : 始点
N+M+1 (=st2) : 流れきれない流量を流す始点
N+M+2 (=gr) : 終点
N+M+3 (=gr2) : 流れきれない流量を流す終点

遷移先	流量	コスト	参考
st → 0～N-1	1	-shirtValue[i]
st → st2	∞	0	シャツに流し切れない量をこっちに流す
st2 → 0～N-1	∞	-MAX	シャツに流し切れない量をこっちに流す
0～N-1 → N～N+M-1	1	-MAX	そういうペアがあれば張る
N～N+M-1→ gr	1	-jeansValue[j]
N～N+M-1→ gr2	∞	0	ジーンズに流しきれない量をこっちに流す
gr2→ gr	∞	-MAX	ジーンズに流しきれない量をこっちに流す

あとは、全部のコストに+MAXをして、流量Kを流す。
で、2K-mcfが答え。
D<Kの場合があるので注意。

struct ShoppingSpree {
    int maxValue(int k, vector <int> shirtValue, vector <int> jeansValue, vector <int> shirtType, vector <int> jeansType) {
        int n = shirtValue.size();
        int m = jeansValue.size();
        int d = shirtType.size(); // d is the number of types

        chmin(k, d);

        ll NG = 1000000;
        MinCostFlow<205, ll> mcf;
        int st = n + m;
        int st2 = n + m + 1;
        int gr = n + m + 2;
        int gr2 = n + m + 3;

        mcf.add_edge(st, st2, 100, NG);
        rep(i, 0, n) mcf.add_edge(st, i, 1, NG - shirtValue[i]);
        rep(i, 0, n) mcf.add_edge(st2, i, 100, 0);
        rep(i, 0, d) mcf.add_edge(shirtType[i], n + jeansType[i], 1, 0);
        rep(i, 0, m) mcf.add_edge(n + i, gr, 1, NG - jeansValue[i]);
        rep(i, 0, m) mcf.add_edge(n + i, gr2, 100, NG);
        mcf.add_edge(gr2, gr, 100, 0);

        ll ans = mcf.mincost(st, gr, k);
        ans = NG * (k * 2) - ans;
        return ans;
    }
};