巢穴

about:blank

P2531

枚举+dfs..
随机化也可以搞

#include <stdio.h>
#include <string>
#include <iostream>
const int MAXN=21;

int n;
int c[MAXN][MAXN];
int d=0,result=-1;
bool hash[MAXN];

void dfs(int x,int step)
{
     if (step==d)
     {
      int ans=0;
      for (int i=1;i<=n;i++)
      {
       if (!hash[i])
       {
        for (int j=1;j<=n;j++)
        {
         if (hash[j])
         {
          ans+=c[i][j];
         }
        }
       }
      }
      if (result<ans) result=ans;
      return;
     }
     for (int i=x;i<=n;i++)
     {
      hash[i]=true;
      dfs(i+1,step+1);
      hash[i]=false;
     }
}
int main()
{
    
    memset(hash,false,sizeof(hash));
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
     for (int j=1;j<=n;j++)
      scanf("%d",&c[i][j]);
    int m=n/2;
    for (int i=1;i<=m;i++)
    {
     d=i;
     dfs(1,0);
    }
     
    printf("%d\n",result);
   // system("pause");
    
    return 0;
}

posted on 2009-11-03 16:05 Vincent 阅读(103) 评论(0)  编辑 收藏 引用 所属分类: 数据结构与算法


只有注册用户登录后才能发表评论。
网站导航:   博客园   博客园最新博文   博问   管理