Density of Power Network(ZOJ 3708)
Problem
The vast power system is the most complicated man-made system and the greatest engineering innovation in the 20th century. The following diagram shows a typical 14 bus power system. In real world, the power system may contains hundreds of buses and thousands of transmission lines.
Network topology analysis had long been a hot topic in the research of power system. And network density is one key index representing the robustness of power system. And you are asked to implement a procedure to calculate the network density of power system.
The network density is defined as the ratio between number of transmission lines and the number of buses. Please note that if two or more transmission lines connecting the same pair of buses, only one would be counted in the topology analysis.
Input
The first line contains a single integer T (T ≤ 1000), indicating there are T cases in total.
Each case begins with two integers N and M (2 ≤ N, M ≤ 500) in the first line, representing the number of buses and the number of transmission lines in the power system. Each Bus would be numbered from 1 to N.
The second line contains the list of start bus number of the transmission lines, separated by spaces.
The third line contains the list of corresponding end bus number of the transmission lines, separated by spaces. The end bus number of the transmission lines would not be the same as the start bus number.
Output
Output the network density of the power system in a single line, as defined in above. The answer should round to 3 digits after decimal point.
Sample Input
3
3 2
1 2
2 3
2 2
1 2
2 1
14 20
2 5 3 4 5 4 5 7 9 6 11 12 13 8 9 10 14 11 13 13
1 1 2 2 2 3 4 4 4 5 6 6 6 7 7 9 9 10 12 14
Sample Output
0.667
0.500
1.429
题解:大体意思就是给你一些公交站牌和一些公交路线,定义一个密度,是路线的条数 / 公交站牌的个数。第一行是公交初始的
位置,下面一行对应的是末位置。如果路线一样去重一下就可以了。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
using namespace std;
int vis[550][550];
int a[550],b[550];
int main()
{
int t,n,i,j,m,w;
double ans;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
for(i=1; i<=m; i++)
scanf("%d",&a[i]);
for(i=1; i<=m; i++)
scanf("%d",&b[i]);
memset(vis,0,sizeof(vis));
w = 0;
for(i=1; i<=m; i++)
{
if(vis[a[i]][b[i]] == 0)
{
vis[a[i]][b[i]] = 1;
vis[b[i]][a[i]] = 1;
w++;
}
}
// cout<<w<<" "<<n<<endl;
ans = (double)w/(double)n;
printf("%.3lf\n",ans);
}
return 0;
}
最新文章
- PHP的变量和常量
- Hibernate(五)__hql语句
- js 停止事件冒泡 阻止浏览器的默认行为(阻止超连接 # )
- swipejs的bug
- angularjs中ng-route和ui-router简单用法的代码比较
- iOS键盘类型
- android studio还不错
- IEEE 802.15.4协议学习之MAC层
- spoj 394
- 破解之关键CALL与关键跳查找方法
- hidden symbol ... is referenced by DSO
- mysql5.6 online ddl—索引
- jq的事件冒泡
- python contextlib 上下文管理器
- C++Primer学习——动态内存
- 剑指Offer--图的操作
- Fuck me
- Offset Management For Apache Kafka With Apache Spark Streaming
- Jenkins插件获取git分支的方法
- 洛谷.2042.[NOI2005]维护数列(Splay)