Posted on 2009-10-03 01:47
Uriel 阅读(232)
评论(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]=s & 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;
}