2014
02-12

# 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

#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 ;
}

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