Description
windy在有向圖中迷路了。 該有向圖有 N 個節點，windy從節點 0 出發，他必須恰好在 T 時刻到達節點 N-1。 現在給出該有向圖，你能告訴windy總共有多少種不同的路徑嗎？ 注意：windy不能在某個節點逗留，且通過某有向邊的時間嚴格為給定的時間。

Input
第一行包含兩個整數，N T。 接下來有 N 行，每行一個長度為 N 的字符串。 第i行第j列為’0’表示從節點i到節點j沒有邊。 為’1’到’9’表示從節點i到節點j需要耗費的時間。

Output
包含一個整數，可能的路徑數，這個數可能很大，只需輸出這個數除以2009的余數。

Sample Input
【輸入樣例一】
2 2
11
00

【輸入樣例二】
5 30
12045
07105
47805
12024
12345

Sample Output
【輸出樣例一】
1

【樣例解釋一】
0->0->1

【輸出樣例二】
852

HINT
30%的數據，滿足 2 <= N <= 5 ； 1 <= T <= 30 。 100%的數據，滿足 2 <= N <= 10 ； 1 <= T <= 1000000000 。

分析：
30%
直接暴力dp
100%
矩陣優化的暴力dp
方程：
f[i][j]表示i時刻，到達j的方案數
f[i+t][k]+=f[i][j] (j,k聯通，路徑的權值是t)

這一次的路徑有權值，這就不能直接用鄰接矩陣來代替轉移矩陣了
但是仔細觀察一下，會發現每條邊的權值不超過9
最多有10個點，
一下想到了拆點（雖然當時沒有浮現這個詞，但是已經想到了把一個點變成好幾個，每個點代表不同的轉移時間）
也就是說，我們的矩陣大概是有100*100

我們把每一個點拆成9個
如果x到y有一條2的邊
那么連接x2—>y1，邊權為1
在同一個點拆出的9個點中xi-1向xi連接邊權為1的邊
注意
如果讀入的矩陣[i][i]=x
那么就從這個點分出來的第x個點連向第一個點

for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){if (!mp[i][j]) continue;int f1=(i-1)*9;int f2=(j-1)*9;H.H[f1+mp[i][j]][f2+1]=1;} for (int i=1;i<=n;i++)for (int j=2;j<=9;j++)H.H[(i-1)*9+j-1][(i-1)*9+j]=1;

最后答案：
H[1][(n-1)*9+1]
這時第一行就是f[T],我們的目標是第n個點拆出來的第一個點，
（第n個點拆出來的第x個點（x！=1），對應的行走時間是T+x-1）

tip

這次是自乘T次
（這就讓我得出了一個結論，T+1，T，T-1試一試就好了）
因為這次矩陣記錄的是初始狀態，一步都沒有走

每次乘出來答案不對，我都以為是我的矩乘寫錯了
后來才發現是我的次數計算錯了

//這里寫代碼片 #include<cstdio> #include<cstring> #include<iostream>using namespace std;const int INF=1e9+1; const int p=2009; int n,T,mp[10][10],f[20],S; char s[10]; struct node{int H[100][100];node operator *(const node &a) const{node ans;for (int i=1;i<=S;i++)for (int j=1;j<=S;j++){ans.H[i][j]=0;for (int k=1;k<=S;k++)ans.H[i][j]=(ans.H[i][j]+H[i][k]*a.H[k][j]%p)%p;}return ans;}void clear(){memset(H,0,sizeof(H));}node KSM(int pp){node ans=(*this),a=(*this);pp--;while (pp){if (pp&1)ans=ans*a;a=a*a;pp>>=1;}return ans;} }; node H,ans;void build() {int i,j;H.clear();for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){if (!mp[i][j]) continue;int f1=(i-1)*9;int f2=(j-1)*9;H.H[f1+mp[i][j]][f2+1]=1;}for (int i=1;i<=n;i++)for (int j=2;j<=9;j++)H.H[(i-1)*9+j-1][(i-1)*9+j]=1; }int main() {scanf("%d%d",&n,&T);for (int i=1;i<=n;i++){scanf("%s",s+1);for (int j=1;j<=n;j++)mp[i][j]=s[j]-'0'; }build();S=n*9;ans=H.KSM(T);printf("%d",ans.H[1][(n-1)*9+1]%p);return 0; }

轉載于:https://www.cnblogs.com/wutongtong3117/p/7673127.html

總結

以上是生活随笔為你收集整理的bzoj1297 [SCOI2009]迷路（矩阵优化）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。