PKU 2531 Network Saboteur(dfs+剪枝||随机化算法)

题目大意：原题链接

给定n个节点,任意两个节点之间有权值,把这n个节点分成A,B两个集合,使得A集合中的每一节点与B集合中的每一节点两两结合(即有|A|*|B|种结合方式)权值之和最大。

标记：A集合:true  B集合:false

解法一：dfs+剪枝

#include<iostream>

#include<cstring>

using namespace std;

int n,ans;

bool in[];

int graph[][];

void dfs(int i,int cursum)

{

    in[i]=true;

    int maxsum=cursum;

    for(int j=;j<=n;j++){

        if(!in[j]) maxsum+=graph[i][j];

        else maxsum-=graph[i][j];

    }

    if(maxsum>ans) ans=maxsum;

    if(maxsum>cursum){//枚举+递归

        for(int j=i+;j<=n;j++)

            dfs(j,maxsum);

    }//如果加进A组没有使得maxsum增大,则不加进去

    in[i]=false;

}

int main()

{

    cin>>n;

    memset(in,,sizeof(in));

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++)

            cin>>graph[i][j];

    }

    ans=;

    dfs(,);

    cout<<ans<<endl;

}

解法二：随机化算法(好神奇的思路)

#include<iostream>

#include<cstdlib>

using namespace std;

const int TLE=;//本题时间限制为2000ms

int main()

{

    int n,m[][];

    cin>>n;

    for(int i=;i<=n;i++){

        for(int j=;j<=n;j++)

            cin>>m[i][j];

    }

    /*Random Algorithm*/

    bool in[]={false};

    int time=*TLE;//使随机次数尽可能大,随机结果尽可能接近最优解

    int maxsum=,cursum=;

    while(time--){

        int x=rand()%n+;//范围：1~n

        in[x]=!in[x];//改变x所在的集合位置

        for(int i=;i<=n;i++){

            if(in[i]!=in[x]) cursum+=m[i][x];

            else  cursum-=m[i][x];

        }

        if(maxsum<cursum) maxsum=cursum;

    }

    cout<<maxsum<<endl;

}