r******e
发帖数: 244 | 1 题目很简单, 有N个不同的点, 用K条线取连接这些点. 问有多少中连法?
比如N= 3, K = 2, 就有三种连法:
1-2-3(3-2-1 和这个是一样的)
2-1-3
2-3-1
应该能推出一个通用公示把,基本是考数学. 楼主我数序奇差, 想不出.
感觉是图论的东西, 不是简单的排列组合. | l*****8
发帖数: 1083 | 2 没必要求公式，写代码，dfs搜索一遍就好了
【在 r******e 的大作中提到】
: 题目很简单, 有N个不同的点, 用K条线取连接这些点. 问有多少中连法?
: 比如N= 3, K = 2, 就有三种连法:
: 1-2-3(3-2-1 和这个是一样的)
: 2-1-3
: 2-3-1
: 应该能推出一个通用公示把,基本是考数学. 楼主我数序奇差, 想不出.
: 感觉是图论的东西, 不是简单的排列组合.
| e********2
发帖数: 495 | 3 C(N*(N-1)/2, K)?
【在 r******e 的大作中提到】
: 题目很简单, 有N个不同的点, 用K条线取连接这些点. 问有多少中连法?
: 比如N= 3, K = 2, 就有三种连法:
: 1-2-3(3-2-1 和这个是一样的)
: 2-1-3
: 2-3-1
: 应该能推出一个通用公示把,基本是考数学. 楼主我数序奇差, 想不出.
: 感觉是图论的东西, 不是简单的排列组合.
| c*******t
发帖数: 123 | 4 我觉得三楼是对的。
N个点，一共可连N*(N-1)/2 个线段。
只连K个， 就是N*(N-1)/2 中选k
【在 r******e 的大作中提到】
: 题目很简单, 有N个不同的点, 用K条线取连接这些点. 问有多少中连法?
: 比如N= 3, K = 2, 就有三种连法:
: 1-2-3(3-2-1 和这个是一样的)
: 2-1-3
: 2-3-1
: 应该能推出一个通用公示把,基本是考数学. 楼主我数序奇差, 想不出.
: 感觉是图论的东西, 不是简单的排列组合.
| E******t
发帖数: 28 | 5 是不是要先看 K> (N-1)是否成立？如果不成立就没有解。
另外是不是dfs 或者bfs都可以？
再者，题目没有说acyclic graph, 剩下的 K-N+1 条线是不是还要随机加回图上去？这
样一下又复杂一层， 总共变成
C(N, (N-1) )*C(K, (N-1))*C(N, (K-N+1))?
即：acyclic graph排法 乘以 这些acyclic graph线段取法 乘以 剩下线段加在图上的
方法数？这里假设了 K<= 2*N。。。
是不是想复杂了？ | r******e
发帖数: 244 | 6 题目保证K > (N - 1), K < N*(N - 1)/2
需要保证最后的图形是个连通图, 即所有点必须连上.不需要是acyclic graph
dfs 和 bfs, 我不知道则么做啊, 先不考虑复杂度的问题.
C(K, (N-1))*C(N, (K-N+1))?
这一段是啥意思???
【在 E******t 的大作中提到】
: 是不是要先看 K> (N-1)是否成立？如果不成立就没有解。
: 另外是不是dfs 或者bfs都可以？
: 再者，题目没有说acyclic graph, 剩下的 K-N+1 条线是不是还要随机加回图上去？这
: 样一下又复杂一层， 总共变成
: C(N, (N-1) )*C(K, (N-1))*C(N, (K-N+1))?
: 即：acyclic graph排法 乘以 这些acyclic graph线段取法 乘以 剩下线段加在图上的
: 方法数？这里假设了 K<= 2*N。。。
: 是不是想复杂了？
| r******e
发帖数: 244 | 7 题目保证K > (N - 1), K < N*(N - 1)/2
需要保证最后的图形是个连通图, 即所有点必须连上.不需要是acyclic graph
dfs 和 bfs, 我不知道则么做啊, 先不考虑复杂度的问题.
C(K, (N-1))*C(N, (K-N+1))?
这一段是啥意思??? | r******e
发帖数: 244 | 8 题目保证K > (N - 1), K < N*(N - 1)/2
需要保证最后的图形是个连通图, 即所有点必须连上.不需要是acyclic graph
dfs 和 bfs, 我不知道则么做啊, 先不考虑复杂度的问题.
C(K, (N-1))*C(N, (K-N+1))?
这一段是啥意思??? | r******e
发帖数: 244 | 9 不能保证连通图
【在 c*******t 的大作中提到】
: 我觉得三楼是对的。
: N个点，一共可连N*(N-1)/2 个线段。
: 只连K个， 就是N*(N-1)/2 中选k
|
|
