SRM 695 div1 med BearKRoads - mayoko’s diary

問題

グラフが与えられる。各頂点にはスコアがある。
このグラフから K 本の辺を選び, 以下のようにスコアを計算する。頂点から少なくとも 1 本の選ばれた辺が伸びている場合, その頂点のスコアを得られ, その和がスコアである。

スコアを最大化せよ。

解法

辺 i のスコアを (x[a[i] ] + x[b[i] ]) とすると, 基本的に辺のスコアが多い順にするのが良いです。

ただ, 選ぶ辺の頂点がかぶっているとスコアが減るのでそこが考えどころですが, 各頂点の次数が 3 以下であることから, 1 つの辺を選んだ時に影響のある辺はたかだか 5 本のみです。
よって, 「上位 5*K 本の辺から K 本を選ぶ」というのを全探索すれば十分です。

35C7 = 6724520

なので, 十分間に合います。

vi x;
vector<pii> P;
int K, N;
bool used[1111];

int dfs(int n, int k, int sum) {
    if (n == N || k == K) return sum; 
    int ret = dfs(n+1, k, sum);
    int u = P[n].first, v = P[n].second;
    bool usedu = used[u], usedv = used[v];
    int plus = 0;
    if (!usedu) plus += x[u];
    if (!usedv) plus += x[v];
    used[u] = true; used[v] = true;
    ret = max(ret, dfs(n+1, k+1, sum+plus));
    if (!usedu) used[u] = false;
    if (!usedv) used[v] = false;
    return ret;
}

class BearKRoads {
public:
    int maxHappy(vector <int> x_, vector <int> a, vector <int> b, int K_) {
        x = x_, K = K_;
        int m = a.size();
        P.resize(m);
        for (int i = 0; i < m; i++)
            P[i] = pii(a[i], b[i]);
        auto cmp = [](const pii& lhs, const pii& rhs) {
            return x[lhs.first] + x[lhs.second] < x[rhs.first] + x[rhs.second];
        };
        sort(P.rbegin(), P.rend(), cmp);
        memset(used, false, sizeof(used));
        N = min<int>(m, 5*K);
        return dfs(0, 0, 0);
    }
};

google で35 choose 7 って打つと 35C7 の計算結果が出てくるの豆知識です。