 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:对每个点,算出起点到该点的走法数F[i]< O( N ) >,和该点到终点的走法数G[i]< O( N ) >,然后枚举每个边< O( M ) >,设s为始点,e为终点,则所有边的F[s]*G[e]的最大值即为答案.时间复杂度为O(N+N+M)In Reply To:我采用回朔加深度优先遍历求入度为0到指定点的走法的总和，为什么总是错呢，麻烦高人指点 Posted by:jsjhoubo at 2007-07-20 15:36:40 > #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;
> }
>
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
