poj 2531

Description

Input

Output

Sample Input

3
0 50 30
50 0 40
30 40 0

Sample Output

90

Source

Northeastern Europe 2002, Far-Eastern Subregion

题目意思是要把n个点随机分成两组，求一组中每个点到另外一组中每个点的距离和的最大值。

枚举每个分组情况，计算就行了。

AC代码：

#include<iostream>
#include<vector>
using namespace std;
int a[30][30];
vector <int> v1;
vector <int> v2;
int main(){
    int n;
    while(cin>>n){
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                cin>>a[i][j];
        int ans=0;
        for(int k=1;k<(1<<n)-1;k++){     //分组情况为 1000..0——1111..0 其中0为一组，1为另一组。
            if(!v1.empty())
                v1.clear();
            if(!v2.empty())
                v2.clear();
            int tmp=k;
            for(int i=1;i<=n;i++){
                if(tmp&1)
                    v1.push_back(i);       //把1组的点保存在v1中
                else
                    v2.push_back(i);       //把0组的点保存在v2中
                tmp=tmp>>1;
            }
            int s=0;
            for(int i=0;i<v1.size();i++)          //求出1组的点到0组的点的距离和
                for(int j=0;j<v2.size();j++)
                    s+=a[v1[i]][v2[j]];           
            if(s>ans)
                ans=s;
        }
        cout<<ans<<endl;
    }
    return 0;
}

poj 2531,布布扣,bubuko.com

poj 2531

原文：http://blog.csdn.net/my_acm/article/details/38237043