首页 > 代码库 > 暴力枚举——通信道路

暴力枚举——通信道路

通信道路

某国正面临严峻的局势,为了确保国内秘密文件传输的安全,该国政府需要统计出国内城市间的通信情况。如果某文件从一个城市送到另一个城市途中恰好只经过两个城市,并且途中的城市没有重复,那么就可以认为该文件的传输是安全的,并且文件传输的起点城市和终点城市可以相同。例如下图所示中,文件传输线路BàCàEàB 和 BàCàEàD是安全的的,而BàCàBàE则是不安全的。

技术分享

 

请计算出该国有多少条安全的传输线路。



Input

多组测试数据,处理到文件结束,对于每组测试数据:

第一行输入两个整数n,m (1≤n≤10000, 1≤m≤200000)

接下来的m行,每行输入两个整数a,b表示城市a,b之间有一条双向的道路。

Output

对于每组测试数据输出一个整数表示安全的传输线路的总数,每组输出占一行。
Sample Input

3 3

1 2

2 3

1 3

 

4 4

1 2

3 4

2 4

1 3
Sample Output

6

8

思路:

直观看起来问题是在找两种可行解的方案总数:

①长度为3的链

②三元环

然而直接找起来很麻烦,我们考虑问题的关键点:

无论是长度为3的链,还是三元环,我们一定有一条中间边。(A-B-C-D,B-C就是中间边)那么如果我们直接枚举这条中间边,那么时间复杂度就是O(m);

那么我们枚举出来这条中间边有什么实际意义呢?

对于这条边而言,其两个端点B.C,B左侧将贡献出degree【B】-1个起点,那么C右侧,就可以贡献出degree【C】-1个终点。那么对于这条边来讲,他能够贡献出来的方案数就有:(degree【B】-1)*(degree【C】-1);

过程累加和,枚举边时间复杂度O(m),显然不会有超时的危险。

自己代码

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<vector>
 4 using namespace std;
 5 vector<int>mp[10050];
 6 int dp[10050];
 7 int main()
 8 {
 9     int n,m;
10     while(~scanf("%d%d",&n,&m))
11     {
12         for(int i=1; i<=n; i++)
13             mp[i].clear();
14         memset(dp,0,sizeof(dp));
15         int x,y;
16         for(int i=0; i<m; i++)
17         {
18             scanf("%d%d",&x,&y);
19             mp[x].push_back(y);
20             mp[y].push_back(x);
21             dp[x]++;
22             dp[y]++;
23         }
24         long long int count_=0;
25         int v;
26         for(int i=1; i<=n; i++)
27         {
28             for(int j=0; j<mp[i].size(); j++)
29             {
30                 v=mp[i][j];
31                 if(dp[i]-1<=0||dp[v]-1<=0)
32                     continue;
33                 count_+=(long long int)(dp[i]-1)*(long long int)(dp[v]-1);
34             }
35         }
36         printf("%lld\n",count_);
37     }
38 
39 }

参考代码

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<vector>
 4 using namespace std;
 5 #define ll long long int
 6 ll degree[10050];
 7 vector<int >mp[10050];
 8 int main()
 9 {
10     int n,m;
11     while(~scanf("%d%d",&n,&m))
12     {
13         for(int i=1; i<=n; i++)
14             mp[i].clear();
15         memset(degree,0,sizeof(degree));
16         for(int i=1; i<=m; i++)
17         {
18             int x,y;
19             scanf("%d%d",&x,&y);
20             mp[x].push_back(y);
21             mp[y].push_back(x);
22             degree[x]++;
23             degree[y]++;
24         }
25         ll output=0;
26         for(int i=1; i<=n; i++)
27         {
28             for(int j=0; j<mp[i].size(); j++)
29             {
30                 int v=mp[i][j];
31                 if(degree[i]-1<=0||degree[v]-1<=0)continue;
32                 output+=(ll)(degree[v]-1)*(ll)(degree[i]-1);
33             }
34         }
35         printf("%lld\n",output);
36     }
37 }

 

暴力枚举——通信道路