Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ Network Saboteur---枚举

Posted on 2009-10-03 01:47 Uriel 阅读(231) 评论(0)  编辑 收藏 引用 所属分类: POJ
这个。。今天CY拿着代码问了我。。我看了题只想到暴力。。
然后帮她看那个版本的代码。。看懂了。。A了。。惭愧。。还不知是哪位大牛的。。感谢大牛的代码
自己的理解可能有误,大牛们不吝指出~
有人找到的话我加个链接
/*Problem: 2531  User: Uriel 
   Memory: 172K  Time: 1047MS 
   Language: C++  Result: Accepted
*/
 

#include
<stdio.h>
#include
<string.h>
#include
<stdlib.h>

int main()
{
    
int n,i,j,k,c[30][30],max,temp,flag[4005];
    scanf(
"%d",&n);
    
int t=1<<(n-1);         //一共2^(n-1)种组合方式 
    memset(c,0,sizeof(c));
    
for(i=0;i<n;i++)
    
{
          
for(j=0;j<n;j++)
          
{
              scanf(
"%d",&c[i][j]);
        }

    }

    max
=-1;    
    
for(i=0;i<t;i++)
    
{
          
int s=i;
          
int f=0;
          
for(j=0;j<n;j++)
          
{
              flag[j]
=& 1;  //不同的标记,分开两组 
              s>>=1;          //将s用二进制表示,正好有n位,用 0 和 1 区分两组 
          }

          
for(j=0;j<n;j++)
          
{
              
if(!flag[j])continue;    //找到标号1的组 
              for(k=0;k<n;k++)
              
{
                
if(flag[k])continue;      //找标号0的组,它们之间的traffic值全部相加 
                  f+=c[j][k];
            }

          }

          
if(max<f)            //更新最大值 
          {
            max
=f;
        }

    }

    printf(
"%d\n",max);
    
return 0;
}



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理