Algoogle

Algorithm for Programming Contest

AOJ 2306 Rabbit Party

Category: AOJ Tag: brute-force

Rabbit Party

問題概要


N人のうさぎの友だちから何匹かをパーティに招待したい.
M組の友だち間に親密度がある.
参加者全てのうさぎについて, 他の参加者との親密度の最小値を求め足しあわせたものをパーティの満足度とするとき, 満足度は最大でいくらになるか.

解法


まず親密度がない(0)になる組が参加者の中に含まれてはいけない(そうなるようなうさぎを追加するとき必ず満足度は下がるから).
そうしたら参加者数を決めてその数になるようなパターンをすべて試す.
M<=100から参加者数は最大でも14で(15C2>100), また条件を満たすパターンはかなり絞られる.

コード


(2306.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a) for(int i=0;i<(int)(a);i++)
#define repit(i,a) for(auto i=begin(a);i!=end(a);i++)
int G[128][128], N, M, fr[128];
vector<int> cand;

int calc(){
    int ret = 0, x;
    repit(i,cand){
        x = 1e9;
        repit(j,cand) if(i!=j) x = min(x,G[*i][*j]);
        ret += x;
    }
    return ret;
}

int rec(int v, int inv){
    if(inv==0) return calc();
    if(v==N) return 0;
    if(fr[v] < inv-1) return rec(v+1,inv);
    repit(i,cand) if(!G[*i][v]) return rec(v+1,inv);
    cand.push_back(v);
    int ret = rec(v+1,inv-1);
    cand.pop_back();
    return max(ret,rec(v+1,inv));
}

int solve(){
    int ans = 0;
    for(int i = 2; i*(i-1)/2<=M; i++)
        ans = max(ans,rec(0,i));
    return ans;
}

void input(){
    cin >> N >> M;
    rep(i,M){
        int u, v, f; cin >> u >> v >> f;
        u--; v--;
        G[u][v] = G[v][u] = f;
        fr[u]++; fr[v]++;
    }
}

int main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments