Posted on 2009-10-03 01:47
Uriel 閱讀(237)
評論(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 區(qū)分兩組
}
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;
}