2531:Network Saboteur

keyword

グラフ　BruteForce　C++

概要

N(<=20)個のノードのグラフがあり、各ノード間にコストが与えられる。ノードを互いに素な2つの集合A,Bに分割してSum_(i in A, j in B) C_ijが最大になるようにしたい。その最大値を求める問題。
サイズが小さいのでBruteForceを考える。分割が2^19(最後の一個は固定)で和をとるのが|A|*20位といささか厳しい。取りあえず投げてみたら何とか通った。多分想定解ではないと思うけど。

int main(){
    int n, i, j, mask, ans=0;
    int traffic[20][20];

    scanf("%d",&n);
    REP(i,n)REP(j,n)scanf("%d",traffic[i]+j);

    REP(mask,(1<<(n-1))){
        int tmp = 0;
        REP(i,n)if(mask & (1<<i))REP(j,n)if(!(mask & 1<<j)){
            tmp += traffic[i][j];
        }
        if(tmp > ans) ans = tmp;
    }

    printf("%d\n",ans);
    return 0;
}