问题描述
X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包，为了安全起见，必须恰好被转发两次到达目的地。该包可能在任意一个节点产生，我们需要知道该网络中一共有多少种不同的转发路径。
源地址和目标地址可以相同，但中间节点必须不同。
如下图所示的网络。
1 -> 2 -> 3 -> 1 是允许的
1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。
输入格式
输入数据的第一行为两个整数N M，分别表示节点个数和连接线路的条数(1<=N<=10000; 0<=M<=100000)。
接下去有M行，每行为两个整数 u 和 v，表示节点u 和 v 联通(1<=u,v<=N , u!=v)。
输入数据保证任意两点最多只有一条边连接，并且没有自己连自己的边，即不存在重边和自环。
输出格式
输出一个整数，表示满足要求的路径条数。
样例输入1
3 3
1 2
2 3
1 3
样例输出1
6
样例输入2
4 4
1 2
2 3
3 1
1 4
样例输出2
10
锦囊1
图论构图，动态规划。
锦囊2
增加两个虚拟点，一个为起始点，一个为目标点。用F[i,j]表示到结点i，经过j次的路径数，则F[i,j]=\sum F[p, j-1]，其中p和i有边相连。最后求目标点e的F[e, 4]。
本题的C++参考代码如下：
1. #include<cstdio>
2. #include<cstring>
3. #include<vector>
4. using namespace std;
5. vector<int> map[10003];
6. int f[10003];
7. int n,m;
8. int ans;
9. void DFS(int start,int k,int c)
10. {
11.     if(c==3)
12.     {
13.         ans++;
14.         return;
15.     }
16.     int len = map[k].size();
17.     for(int i=0;i<len;i++)
18.     {
19.        
20.         if(f[map[k][i]]==0 || (c==2 && map[k][i]==start))
21.         {
22.             f[map[k][i]] = 1;
23.             DFS(start,map[k][i],c+1);
24.             if(c==2 && map[k][i]==start)
25.             f[map[k][i]] = 1;
26.             else
27.                 f[map[k][i]] = 0;
28.
29. cstring转为int        }
30.     }
31. }
32. int main()
33. {
34.     int i;
35.     while(scanf("%d%d",&n,&m)!=EOF)
36.     {
37.         int u,v;
38.         ans = 0;
39.         for(i=0;i<=n;i++)
40.             map[i].clear();
41.         for(i=0;i<m;i++)
42.         {
43.             scanf("%d%d",&v,&u);
44.             map[v].push_back(u);
45.             map[u].push_back(v);
46.         }
47.         for(i=1;i<=n;i++)
48.         {
49.             memset(f,0,sizeof(f));
50.             f[i] = 1;
51.             DFS(i,i,0);
52.         }
53.        
54.         printf("%d\n",ans);
55.     }
56.     return 0;
57.    
58.    
59. }
本题的C参考代码如下：
1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<string.h>
4. struct Node
5. {
6.     int data;
7.     struct Node *pNext;
8. };
9. struct Node tab[10001];
10. int visit[10001]={0};
11. int way[10001]={0};
12. int cnt=0;
13. void Insert(int n,int x);
14. void Init(int n);
15. void dfs(int x,int n,int s);
16. int main()
17. {
18.     int n,m,u,v,i;
19.     scanf("%d%d",&n,&m);
20.     Init(n);
21.     while(m--)
22.     {
23.         scanf("%d%d",&u,&v);
24.         Insert(u,v);
25.         Insert(v,u);
26.     }
27.     for(i=1;i<=n;i++)
28.     {
29.         memset(visit,0,sizeof(int)*n);
30.         dfs(i,0,i);
31.     }
32.     printf("%d\n",cnt);
33.     return 0;
34. }
35. void dfs(int x,int n,int s)
36. {
37.     visit[x]=1;
38.     way[n]=x;
39.     struct Node *p=&tab[x];
40.     if(n>=3)
41.     {
42.         cnt++;
43.         return ;
44.     }
45.     while((p=p->pNext)!=NULL)
46.     {
47.         if((visit[p->data]!=1)||(p->data==s&&n==2))
48.         {
49.             dfs(p->data,n+1,s);
50.             if(p->data!=s)
51.             {
52.                 visit[p->data]=0;
53.             }
54.            
55.         }
56.     }
57. }
58. void Init(int n)
59. {
60.     int i;
61.     for(i=1;i<=n;i++)
62.     {
63.         tab[i].data=i;
64.         tab[i].pNext=NULL;
65.     }
66. }
67.
68. void Insert(int n,int x)
69. {
70.     struct Node *p=&tab[n];
71.     while(p->pNext!=NULL)
72.     {
73.         p=p->pNext;
74.     }
75.     struct Node *new=(struct Node *)malloc(sizeof(struct Node));
76.     p->pNext=new;
77.     new->data=x;
78.     new->pNext=NULL;
79. }

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。