> 0ms。。。
#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:有幸看到一个大牛程序 郁闷的是看不太懂…… (1059) acmer1183 2010-04-07 23:12:26
  • Re:有幸看到一个大牛程序 郁闷的是看不太懂…… (0) acmer1183 2010-04-08 23:16:38
    • 好算法呀 终于懂了 些算法O(2^n) , DFS O(N!) (0) acmer1183 2010-04-08 23:17:01
• Re:一个剪枝16ms，0ms是怎么出来的？ (20) 0801050332 2011-02-14 23:55:20
• Re:一个剪枝16ms，0ms是怎么出来的？ (1059) 2216652925 2012-04-01 20:56:45