Problem Description

題目給出一個(gè)有n個(gè)節(jié)點(diǎn)的有向圖，求該有向圖中長(zhǎng)度為k的路徑條數(shù)。方便起見(jiàn)，節(jié)點(diǎn)編號(hào)為1,2,…,n，用鄰接矩陣表示該有向圖。該有向圖的節(jié)點(diǎn)數(shù)不少于2并且不超過(guò)500.

?

?

例如包含兩個(gè)節(jié)點(diǎn)的有向圖，圖中有兩條邊1 → 2 ,2 → 1 。

長(zhǎng)度為1的路徑有兩條：1 → 2 和 2 →1 ；

長(zhǎng)度為2的路徑有兩條：1 → 2 → 1和2 → 1 → 2 ；

偷偷告訴你也無(wú)妨，其實(shí)這個(gè)圖無(wú)論k取值多少 ( k > 0 )，長(zhǎng)度為k的路徑都是2條。

Input

每組輸入第一行是有向圖中節(jié)點(diǎn)的數(shù)量即鄰接矩陣的行列數(shù)n和Ｋ。接下來(lái)n行n列為該圖的鄰接矩陣。

Output

輸出一個(gè)整數(shù)，即為圖中長(zhǎng)度為k的路徑的條數(shù)。

樣例輸入

4 2

0 1 1 0

0 0 1 0

0 0 0 1

1 0 0 0

樣例輸出

6

?

解法：假設(shè)從Ｕ出發(fā)到Ｖ的長(zhǎng)度為Ｋ的路徑總數(shù)為Ｇｋ［Ｕ］［Ｖ］，那么ｋ＝１時(shí)和邊值相同，因此Ｇ１就等于圖的鄰接矩陣．

假設(shè)已經(jīng)得到Ｇｋ１和Ｇｋ２，那么Ｇ（ｋ１＋ｋ２）　＝　Ｇｋ１＊Ｇｋ２．

Ｇｋ　＝　（Ｇ１）＾ｋ．

所以此時(shí)候就可以用矩陣快速冪來(lái)進(jìn)行求解．

?

1 #include <iostream> 2 #include <vector> 3 #define ll long long int 4 #define mod 10007 5 using namespace std; 6 typedef vector<ll> vec; 7 typedef vector<vec> mat; 8 9 mat mul(mat &a,mat &b){ 10 mat c(a.size(),vec(b[0].size())); 11 for(int i=0;i<a.size();i++){ 12 for(int j=0;j<b[0].size();j++){ 13 for(int k=0;k<b.size();k++){ 14 c[i][j] = (c[i][j]+a[i][k]*b[k][j]); 15 } 16 } 17 } 18 return c; 19 } 20 21 mat pow(mat a,int n){ 22 mat c(a.size(),vec(a.size())); 23 for(int i=0;i<a.size();i++) 24 c[i][i] = 1; 25 while(n){ 26 if(n&1) 27 c = mul(c,a); 28 a = mul(a,a); 29 n>>=1; 30 } 31 return c; 32 } 33 34 int main(){ 35 int n,k; 36 cin>>n>>k; 37 mat a(n,vec(n)); 38 for(int i=0;i<n;i++){ 39 for(int j=0;j<n;j++){ 40 cin>>a[i][j]; 41 } 42 } 43 a = pow(a,k); 44 int ans = 0; 45 for(int i=0;i<n;i++){ 46 for(int j=0;j<n;j++){ 47 ans+=a[i][j]; 48 } 49 } 50 cout<<ans<<endl; 51 return 0; 52 }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/zllwxm123/p/9540391.html

總結(jié)

以上是生活随笔為你收集整理的图中长度为k的路径的计数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。