程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SPOJ104 Highways,生成樹計數

SPOJ104 Highways,生成樹計數

編輯:C++入門知識

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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved