Posted on 2009-10-03 01:47
Uriel 閱讀(237)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
POJ
這個(gè)。。今天CY拿著代碼問(wèn)了我。。我看了題只想到暴力。。
然后幫她看那個(gè)版本的代碼。。看懂了。。A了。。慚愧。。還不知是哪位大牛的。。感謝大牛的代碼
自己的理解可能有誤，大牛們不吝指出~
有人找到的話我加個(gè)鏈接
/**//*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; //不同的標(biāo)記，分開(kāi)兩組
s>>=1; //將s用二進(jìn)制表示，正好有n位，用 0 和 1 區(qū)分兩組
}
for(j=0;j<n;j++)
{
if(!flag[j])continue; //找到標(biāo)號(hào)1的組
for(k=0;k<n;k++)
{
if(flag[k])continue; //找標(biāo)號(hào)0的組，它們之間的traffic值全部相加
f+=c[j][k];
}
}
if(max<f) //更新最大值
{
max=f;
}
}
printf("%d\n",max);
return 0;
}