D - バレンタインデー

時間制限 : 2sec / メモリ制限 : 256MB

問題文

あるクラスには女子が N 人、男子が M 人いる。女子には 1 から N までの出席番号が、男子には 1 から M までの出席番号が割り当てられている。

幸運のキューピットはここから女子 P 人と男子 Q 人からなる、1 つの旅行グループを作る。

N 人の女子は合わせて R 個のチョコレートを持っており、チョコレートには 1 から R までの番号が付けられている。

チョコレート i(1≦i≦R) は出席番号が xi である女子が持っており、旅行中に出席番号が yi である男子に渡す予定である。そのため旅行グループに出席番号が xi である女子と出席番号が yi である男子が両方含まれていた場合に限り渡すことができる。無事にチョコレート i が渡された場合の幸福度は zi である。

無事に渡されたチョコレートによる幸福度の合計値として考えられる最大値はいくらか。

note

女の子を固定して全列挙　すると　(2n)くらいが女の子のパターンであとは貪欲に解けばいいので、O( (2n) _n_m )で十分間にあう

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
#define N_MAX 19
#define M_MAX 19
#define ll long long

struct chocho
{
    int to;
    int happiness;
};

int main(){
    int n, m, p, q, r;
    vector<chocho> G[M_MAX];

    cin >> n >> m >> p >> q >> r;

    for (int i = 0; i < r; ++i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--;
        chocho tmp = {y, z};
        G[x].push_back(tmp);
    }

    ll ans = 0;
    for (int i = 0; i < 1 << n; ++i)
    {
        int count = 0;
        for (int j = 0; j < n; ++j)
        {
            if(i >> j & 1) count++;
        }
        if(count == p){
            vector<int> happy(m, 0);
            for (int j = 0; j < n; ++j)
            {
                if(i >> j & 1){
                    for (int k = 0; k < G[j].size(); ++k)
                    {
                        happy[G[j][k].to] += G[j][k].happiness;
                    }
                }
            }
            sort(happy.begin(), happy.end(), greater<int>());
            ll tmp = 0;
            for (int j = 0; j < q ; ++j)
            {
                tmp += happy[j];
            }
            ans = max(tmp, ans);
        }
    }

    cout << ans << endl;

}

TakefumiYamamura / programming_contest

AtCoder Beginner Contest 018 #28

D - バレンタインデー

問題文

note