Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

C语言 AC代码 dfs

Posted by sunny1995 at 2014-12-11 19:43:46 on Problem 1564
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int m,n,x[102]={0},total=0,cnt=0,ans[1002]={0},k,c=0,ans2[2000][100]={{0}},num[2000]={0};

void dfs(int a,int b)
{
    int a0,b0,i;
    if (b==0)
	{
		total++;
		for (k=0;k<=cnt-1;k++)
			ans2[c][k]=ans[k];
		num[c]=cnt;
		c++;
	}
    for (i=a+1;i<=m-1;i++)
	{
        b0=b-x[i];
		if (b0>=0)
		{
			ans[cnt]=x[i];
			cnt++;
			a0=i;
			dfs(a0,b0);
			cnt--;
		}
    }
}

int main()
{
    int j,i0,j0=0,p[1000],k0;
	do{
		scanf("%d%d",&n,&m);
		if (n==0)
			break;
		total=0;
		memset(ans2,0,sizeof(ans2));
		memset(ans,0,sizeof(ans));
		cnt=0;
		c=0;
		for (j=0;j<=m-1;j++)
			scanf("%d",&x[j]);
		dfs(-1,n);
		memset(p,1,sizeof(p));
		for (i0=0;i0<=total-1;i0++)
		{
			if (!p[i0])
				continue;
			for (j0=i0+1;j0<=total-1;j0++)
			{
            if (!p[j0])
				continue;
			if (num[i0]==num[j0])
			{
    			for (k0=0;k0<=num[i0]-1;k0++)
				{
		    	if (ans2[i0][k0]!=ans2[j0][k0])
				{
	     			p[j0]=1;
					goto l1;
				}}
				p[j0]=0;
                l1:   ;
			}
   		}
		}
		printf("Sums of %d:\n",n);
		if (total==0)
			printf("NONE\n");
		else
		{
			for (i0=0;i0<=total-1;i0++)
			{
				if (p[i0])
				{
					for (j0=0;j0<=num[i0]-2;j0++)
					{
						printf("%d+",ans2[i0][j0]);
					}
					printf("%d",ans2[i0][num[i0]-1]);
					printf("\n");
				}
			}
		}
	}while(1);
    return 0;
}
注意判重,多用前面评论里的陷阱数据试试

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator