#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define max 5020
bool graph[max][max];
bool visited[max];
int sum=0;
bool in[max];
int n;
void backtrack(int t)
{
	int i;
	if(t==n)
	{
		sum++;
		return;
	}
	for(i=1;i<=n;i++)
	{
		if(graph[t][i] && !visited[i])
		{
			visited[i]=true;
			backtrack(i);
			visited[i]=false;
		}
	}
}
int main()
{
	int i,j,k,m;
	//FILE *fp;
	//fp=fopen("c:\\hb.txt","r");
    memset(graph,false,sizeof(graph));
	memset(in,true,sizeof(in));
	//fscanf(fp,"%d%d",&n,&m);
	scanf("%d%d",&n,&m);
	if(n==1)
		printf("0\n");    
	while(scanf("%d %d", &j, &k) !=EOF)
	{
		graph[j][k]=true;
		in[k]=false;
	}
	memset(visited,false,sizeof(visited));
	for(i=1;i<=n;i++)
		if(in[i])
		{
			visited[i]=true;		
			backtrack(i);
		}
	printf("%d\n",sum);
	return 0;
}

• Re:对每个点,算出起点到该点的走法数F[i]< O( N ) >,和该点到终点的走法数G[i]< O( N ) >,然后枚举每个边< O( M ) >,设s为始点,e为终点,则所有边的F[s]*G[e]的最大值即为答案.时间复杂度为O(N+N+M) (952) ecjtuxsyuan 2008-07-21 16:13:11
  • Re:Yeah……厉害厉害 (0) cuixin 2010-03-07 12:47:52