本文主要是介绍HRBUST 1789 通信道路（思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
| 通信道路 | ||||||
| ||||||
| Description | ||||||
| 某国正面临严峻的局势，为了确保国内秘密文件传输的安全，该国政府需要统计出国内城市间的通信情况。如果某文件从一个城市送到另一个城市途中恰好只经过两个城市，并且途中的城市没有重复，那么就可以认为该文件的传输是安全的，并且文件传输的起点城市和终点城市可以相同。例如下图所示中，文件传输线路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 | ||||||
| Author | ||||||
| 周洲 @hrbust |
假设我们有 A -- B -- C -- D ，我们只需枚举 B -- C 的这一条边，再将B和C的度减一相乘，即为经过B、C所有情况数
#include<bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
struct xx
{int u,v;
}a[N];
int f[N];
int main()
{int m,n;while(scanf("%d%d",&n,&m)==2){memset(f,0,sizeof(f));for(int i=0;i<m;i++){scanf("%d%d",&a[i].u,&a[i].v);f[a[i].u]++,f[a[i].v]++;}int ans=0;for(int i=0;i<m;i++){if(a[i].u&&a[i].v)ans+=2*(f[a[i].u]-1)*(f[a[i].v]-1);}printf("%d\n",ans);}
}
这篇关于HRBUST 1789 通信道路（思维）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
