首页 > 搜索 > DFS搜索 > hdu 2625 Say love to you once again-DFS-[解题报告]C++
2014
02-12

hdu 2625 Say love to you once again-DFS-[解题报告]C++

Say love to you once again

问题描述 :

Say love to you once again——I remember that day, you’re sitting in front of me. Obviously your wishes, waiting for my performance. I said some other day, when I have sufficient time
, I would certainly give you a perfect declaration of love. I would like to seize every moment, I am afraid that the story is yesterday. I came to realize that neglect is the largest defect of me, but it was to late. I really want to say love to you once again. I am willing to give up everything only in exchange for you. If time can turn the clock back for you. I will hold your hands once again, say, I love you!

It is an old legend.
If you can solve this problem, god will give you a chance to say love to your darling once again, so, yifenfei, seize the chance.
There are N plane in the sky, and every one can attack each other. Now, we assigned each has a number i (1 <= i <= N), plane i and plane j can produce Aij points of hurt. Your task is to divide N planes into two groups. Each group in itself don’t produce any point of hurt, but plane between two groups will produces hurt.
Please maximize sum of all the hurt.

输入:

For each case, first input a N(2 <= N <= 25), represent the number of planes in the sky, then a matrix A, (Aij = Aji, Aii = 0 for all i,j<= N), Aij represents the hurt between plane i and plane j.

输出:

For each case, first input a N(2 <= N <= 25), represent the number of planes in the sky, then a matrix A, (Aij = Aji, Aii = 0 for all i,j<= N), Aij represents the hurt between plane i and plane j.

样例输入:

3
0 150 20
150 0 140
20 140 0

样例输出:

290.

 

http://acm.hdu.edu.cn/showproblem.php?pid=2625

随便写出一个dfs然后猥琐随机化法剪枝,第一次AC的战绩是1/18,还跑了700+ms,随机50w次成功率还这么低。。。最近rp真是太烂了有木有。。。

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std ;
int map[30][30] ;
int n ;
int ans ;
int vis[30] ;
void dfs(int d)
{
    if(d==n)
    {
        int temp=0 ;
        for(int i=0;i<n;i++)
            if(vis[i])
                for(int j=0;j<n;j++)
                    if(!vis[j])
                        temp+=map[i][j] ;
        if(ans<temp)
            ans=temp ;
        return ;
    }
    vis[d]=1 ;
    dfs(d+1) ;
    vis[d]=0 ;
    dfs(d+1) ;
}
int main()
{
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
                scanf("%d",&map[i][j]) ;
        memset(vis,0,sizeof(vis)) ;
        ans=0 ;
        if(n<20)
            dfs(0) ;
        else
        {
            int times=500000 ;
            srand(time(0)) ;
            while(times--)
            {
                vis[rand()%n]^=1 ;
                int temp=0 ;
                for(int i=0;i<n;i++)
                    if(vis[i])
                        for(int j=0;j<n;j++)
                            if(!vis[j])
                            temp+=map[i][j] ;
                if(ans<temp)
                    ans=temp ;
            }
        }
        printf("%d.\n",ans) ;
    }
    return 0 ;
}

 

解题转自:http://www.cnblogs.com/xiaohongmao/archive/2012/06/07/2539860.html


  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。