ABC 018 D

今日はこの問題を解きました。

abc018.contest.atcoder.jp

女子がn人、男子がm人います。またチョコレートがr個あり、それぞれどの女子からどの男子へ渡されるものか、そのチョコレートが渡された場合どのくらい幸福度が増えるかが決まっています。女子p人、男子q人のグループを作って、そのグループに渡す側渡される側どちらもいるようなチョコレートはすべて渡されるとします。幸福度の合計が最大になるようにグループのメンバーを選んだとき、その幸福度を求めましょう、という問題です。

最初二分グラフが思い浮かびました。これをもとに、クラスカル法のように貪欲に求められないかなと考えて実装しました。が、サンプル二つ目で引っかかりました。ちょっと考えたら、確かにただの貪欲法ではだめだなと気づきました。

解法が思いつかなかったので大人しく解説を見ました。
回答は、女子だけメンバーを固定して、その中で幸福度が最大になるように男子を選ぶ、というものでした。
女子が決まれば男子がそれぞれグループに選ばれた場合に得られる幸福度が1つに決まり、得られる幸福度が大きい男子から順にグループに選べばうまくいきます。納得です。
回答はこんな感じになりました。

    #include <cstdio>
    #include <iostream>
    #include <cmath>
    #include <cstring> 
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <cstdlib>
    #include <map>
    #include <queue>
    #include <utility>
    #include <vector>
    #include <set>
    #include <memory.h>
    #include <iomanip>
    #include <bitset>
    #include <list>
    #include <stack>
     
    using namespace std;
     
    #define pai 3.14159265359
    #define mod 1000000007
     
    int n, m, p, q, r;
    vector<vector<pair<int, int> > > chocolate(20);
     
    int main()
    {
        cin >> n >> m >> p >> q >> r;
        for(int i = 0; i < r; i++){
            int x, y, z;
            cin >> x >> y >> z;
            x--;
            y--;
            chocolate[x].push_back(make_pair(y, z));
        }
        long long int ans = 0;
        for(int i = 0; i < (1 << n); i++){
            int girlnum = 0;
            int happinessofboy[20] = {};
　　　　　　// hapinnessofboy[i] : i番目の男子が得られる幸福度
            for(int j = 0; j < n; j++){
                if((i & (1 << j)) != 0){
                    girlnum++;
                    for(int k = 0; k < chocolate[j].size(); k++){
                        happinessofboy[chocolate[j][k].first] += chocolate[j][k].second;
                    }
                }
            }
            if(girlnum != p) continue;
            priority_queue<int> qu;
            for(int j = 0; j < m; j++){
                qu.push(happinessofboy[j]);
            }
            long long int nowans = 0;
            for(int i = 0; i < q; i++){
                nowans += qu.top();
                qu.pop();
            }
            ans = max(nowans, ans);
        }
        cout << ans << endl;
        return 0;
    }

グループに入っている女子の組み合わせはビットで表現しました。1がp個たっている場合のみ考えればいいです。ビットで表すときに、女子の番号が1から始まっていると不便なので0から始めるようにxの値を1減らしました。ついでにyも減らしました。
あとはそれぞれの女子が渡すチョコレートをみて、相手の男子が得られる幸福度を増加させます。最後に男子のうち得られる幸福度が大きいものから順にq人選べばよいです。