> #include<stdio.h>
> int map[25][25];
> int in[25];
> int out[25];
> int n,ans;
> void dfs(int k,int s,int ni,int no)
> {
> 	int i,sum;
> 	if(s>=ans)
> 		return;
>         sum=0;
> 	for(i=1;i<=ni;i++)
> 		sum+=map[in[i]][k];
> 	if(k==n)
> 	{
> 		if(s+sum<ans)
> 			ans=s+sum;
> 	}
> 	else
> 	{
> 		in[ni+1]=k;
> 		dfs(k+1,s+sum,ni+1,no);
> 	}
> 	sum=0;
> 	for(i=1;i<=no;i++)
> 		sum+=map[out[i]][k];
> 	if(k==n)
> 	{
> 		if(s+sum<ans)
> 			ans=s+sum;
> 	}
> 	else
> 	{
> 		out[no+1]=k;
> 		dfs(k+1,s+sum,ni,no+1);
> 	}
> 	return;
> }
> int main()
> {
> 	int i,j,k,p=0,q=0;
> 	scanf("%d",&n);
> 	ans=0;
> 	for(i=1;i<=n;i++)
> 	{
> 		for(j=1;j<=n;j++)
> 		{
> 			scanf("%d",&map[i][j]);
> 			ans+=map[i][j];
> 		}
> 	}
> 	k=ans/2;
> 	for(i=1;i<=n/2-1;i++)
> 	{
> 		for(j=1;j<=n/2-1;j++)
> 			p+=map[i][j];
> 	}
> 	p=p/2;
> 	for(i=n/2;i<=n;i++)
> 	{
> 		for(j=n/2;j<=n;j++)
> 			q+=map[i][j];
> 	}
> 	q=q/2;
> 	ans=p+q;
> 	in[1]=1;
> 	dfs(2,0,1,0);
> 	printf("%d\n",k-ans);
> 	return 0;
> }

• Re:有幸看到一个大牛程序 郁闷的是看不太懂…… (0) acmer1183 2010-04-08 23:16:38
  • 好算法呀 终于懂了 些算法O(2^n) , DFS O(N!) (0) acmer1183 2010-04-08 23:17:01