2015苏州大学ACM-ICPC集训队选拔赛(1) 1007
2024-09-08 02:27:18
连通图
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65535/32768K (Java/Other)
Total Submission(s) : 70 Accepted Submission(s) : 29
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
首先我们了解无向图中的两个概念:
(1)完全图:n 个点的图中任意两个点之间都有一条边相连,所以有 n*(n-1)/2 条边。(如下图)
(2)连通图:图中任意两个点之间都有路径,所以至少得有 (n-1) 条边。(如下图)
现在给出一个 n 个点的完全图,要从其中选择 k 条不同的边,问这 n 个点与选择的边能构成连通图的概率?
(1)完全图:n 个点的图中任意两个点之间都有一条边相连,所以有 n*(n-1)/2 条边。(如下图)
(2)连通图:图中任意两个点之间都有路径,所以至少得有 (n-1) 条边。(如下图)
现在给出一个 n 个点的完全图,要从其中选择 k 条不同的边,问这 n 个点与选择的边能构成连通图的概率?
Input
多组输入数据。
每组数据一行,有两个数 n 和 k。
数据范围:1 <= n <= 4,0 <= k <= n*(n-1)/2 。
每组数据一行,有两个数 n 和 k。
数据范围:1 <= n <= 4,0 <= k <= n*(n-1)/2 。
Output
对于每一组数据输出一行,代表概率,四舍五入到小数点后2位。(即:用 %.2f 输出)
Sample Input
1 0
2 0
Sample Output
1.00
0.00
Author
Natureal
这个题目数据1到4 直接算出来就好了
#include<stdio.h>
//#include<bits/stdc++.h>
#include<string.h>
#include<iostream>
#include<math.h>
#include<sstream>
#include<set>
#include<queue>
#include<map>
#include<vector>
#include<algorithm>
#include<limits.h>
#define inf 0x3fffffff
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define ULL unsigned long long
using namespace std;
const int maxn=35;
ULL dp[maxn][maxn*maxn];
int C(int n,int m)
{
if(n<m) return 0;
int ans=1;
for(int i=0;i<m;i++) ans=ans*(n-i)/(i+1);
return ans;
}
int main()
{
int n,k;
float f;
while(cin>>n>>k)
{
if(n==1&&k==0)
{
puts("1.00");
}
else if(n!=1&&k==0)
{
puts("0.00");
}
else if(n==2&&k==1||n==3&&k==2||n==3&&k==3)
{
puts("1.00");
}
else if(k<(n-1))
{
puts("0.00");
}
else if(n==4&&k>=5)
{
puts("1.00");
}
else if(n==4&&k==3)
{
printf("%.2f\n",16*1.0/20);
}
else
{
printf("1.00\n");
}
}
return 0;
}
最新文章
- HTML+CSS代码橙色导航菜单
- 百度地图helloworld程序问题
- Rails 4.0 移除了 XML 参数解析器。若要使用请加入 actionpack-xml_parser
- ACM/ICPC 之 SPFA范例两道(POJ3268-POJ3259)
- confluence重置admin密码
- hung_task_timeout_secs 和 blocked for more than 120 seconds
- Azure HDInsight与Hadoop周边系统集成
- jQuery获取鼠标移动方向2
- Linux Shell脚本入门--grep命令详解
- POJ训练计划2418_Hardwood Species(Trie树)
- Linux常见目录及其作用
- java8完全解读二
- tomcat 反代配置
- 从composer上在本地创建一个项目
- Use Slim to overview model in Tensorflow like model.summary() in Keras
- c 字符数组与字符串
- 多线程——Executor、ExecutorService、Executors三者的区别
- [转]Docker 生产环境之配置容器 - 限制容器资源
- Educational Codeforces Round 54 (Rated for Div. 2) Solution
- Python3制作中文词云图