aoj2306:Rabbit Party

問題文

Rabbit Party | Aizu Online Judge

解法

招待するやつらだけを取り出したグラフはクリークになっていたほうがよい。
(クリークになっていない場合は、適切に頂点を取り除けばスコアを増やせることが分かるので、クリークの状態が極大となる)

これにより、考えられるクリークをすべて見ることができればよくなる。

ここで、小さいグラフに対する最大クリーク問題のテク(頂点の次数に着目して再帰的にやるやつ)を応用(流用？)すれば、この問題も解ける。

指数時間アルゴリズム入門
↑ググったらたまたま見つけたやつですが、分かりやすいのでお勧めです

コード

#include<bits/stdc++.h>
using namespace std;

#define int long long
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define all(v) (v).begin(),(v).end()
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define pb push_back
#define fi first
#define se second
template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

struct edge{
    int to,cost;
    edge(int to,int cost):to(to),cost(cost){}
};

int N,M;
vector<edge>G[100];
int T[100][100];
const int L=12;

int ma=0;
bool used[100];
int deg[100];

int calc(vint &v){
    if(v.size()<=1)return 0;
    int sum=0;
    for(auto a:v){
        int t=1001001001;
        for(auto b:v)if(a!=b)chmin(t,T[a][b]);
        sum+=t;
    }
    return sum;
}

void dfs(){
    memset(deg,0,sizeof(deg));
    rep(i,N){
        if(used[i])continue;
        for(auto e:G[i])if(!used[e.to])deg[i]++;
        if(deg[i]>L)continue;
        vector<int>lis;
        for(auto e:G[i])if(!used[e.to])lis.pb(e.to);
        rep(j,1<<lis.size()){
            vector<int>v={i};
            rep(k,lis.size()){
                if(j>>k&1)v.pb(lis[k]);
            }
            chmax(ma,calc(v));
        }
        used[i]=true;
        dfs();
        return;
    }

    vector<int>v;
    rep(i,N)if(!used[i])v.pb(i);
    rep(i,1<<v.size()){
        vector<int>u;
        rep(j,v.size())if(i>>j&1)u.pb(v[j]);
        chmax(ma,calc(u));
    }
}

signed main(){
    cin>>N>>M;
    rep(i,M){
        int a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        G[a].pb(edge(b,c));
        G[b].pb(edge(a,c));
        T[a][b]=T[b][a]=c;
    }

    dfs();
    cout<<ma<<endl;
    return 0;
}