SPOJ104 Highways，生成树计数 - c++编程基础

TOP

SPOJ104 Highways，生成树计数

2015-07-20 17:35:43 来源: 作者: 【大中小】浏览:2次

Tags：SPOJ104 Highways 生成计数

高速公路（SPOJ104 Highways）

一个有n座城市的组成国家，城市1至n编号，其中一些城市之间可以修建高速公路。现在，需要有选择的修建一些高速公路，从而组成一个交通网络。你的任务是计算有多少种方案，使得任意两座城市之间恰好只有一条路径？

数据规模：1≤n≤12。

生成树计数

算法步骤：

1、构建拉普拉斯矩阵

Matrix[i][j] =

degree(i) , i==j

-1，i-j有边

0，其他情况

2、去掉第r行，第r列（r任意）

3、计算矩阵的行列式

#include 
#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; typedef long long ll; const int maxn = 105; const int maxm = 100005; const int INF = 1e9; int degree[maxn]; ll g[maxn][maxn]; int n, m; ll det(ll a[][maxn], int n) { ll ret = 1; for(int i=1; i


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：nyoj 1078 汉诺塔（四）[二分图 \|..	下一篇：HUD 5056 Boring count

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: