圖的存儲有鄰接矩陣，那么他就具備一些矩陣的性質，設有一個圖的demo[100][100];那么demo[M][N]就是M—>N的距離，若經過一次松弛操作demo[M][N]=demo[M][K]+demo[K][N],即為demo[M][N]經過了兩條條邊的最小距離，floyd是? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?demo[M][N]=Min(demo[M][K]+demo[K][N]，demo[M][N]）,有可能兩點之間直接距離最短，不經過第三邊，那我們不考慮不經過兩點之間的情況，那么demo[M][N]等于??demo[M][K]+demo[K][N] 枚舉K的最小值，于是出現了一類問題，叫做兩點之間經過N條邊的最短距離，那么類比矩陣乘法，矩陣乘法是求和，我們在這里是求最小值，那么可以改造矩陣乘法得出，不是Floyd，K放在外面和里面沒有區別，放外面像是Floyd，放里面就是標準的矩陣乘法，因為這個只用一次，所有對于枚舉的狀態是等價的。

for(int k=1; k<=cnt; k++){for(int i=1; i<=cnt; i++){for(int j=1; j<=cnt; j++){c[i][j]=Min(a[i][k]+b[k][j],c[i][j]);}}}

每做一次類矩陣乘法，就代表將M，N松弛后多一條經過邊，那么經過T次松弛后就會得到N，M經過T條邊的最短距離，既然是類矩陣乘法，是不是遵循結合律呢？答案是的。對于矩陣,前面是經過T條邊的最小值，后邊是經過W條邊的最小值，想乘代表經過了T+W條邊的最小值，因為每進行一次都是插入一個點，即使點重復，那么他也會有環形出現，但還是經過了T+W條邊，如此，我們可以利用矩陣快速冪求解其經過N條邊之后的最小值，那么我們會發現矩陣跟圖的是密不可分，一定還會有其他的特點去等待發現，它還可以用于求解圖的生成樹問題，下次更新。

本思想可以解決POJ3613，好像現在題沒了，給一個網站https://www.acwing.com/problem/content/347/，代碼附在下方。

#include<iostream> #include<queue> #include<algorithm> #include<set> #include<cmath> #include<vector> #include<map> #include<stack> #include<bitset> #include<cstdio> #include<cstring> #define Swap(a,b) a^=b^=a^=b #define cini(n) scanf("%d",&n) #define cinl(n) scanf("%lld",&n) #define cinc(n) scanf("%c",&n) #define cins(s) scanf("%s",s) #define coui(n) printf("%d",n) #define couc(n) printf("%c",n) #define coul(n) printf("%lld",n) #define speed ios_base::sync_with_stdio(0) #define Max(a,b) a>b?a:b #define Min(a,b) a<b?a:b #define mem(n,x) memset(n,x,sizeof(n)) #define INF 0x3f3f3f3f #define maxn 100010 #define esp 1e-9 #define mp(a,b) make_pair(a,b) using namespace std; const int N=300; #define clr(a) memset(a,0,sizeof(a)) int a[N][N],temp[N][N],ans[N][N]; int used[10*N]; int p[10*N]; void floyed(int a[][N],int b[][N],int c[][N],int cnt) {for(int k=1; k<=cnt; k++){for(int i=1; i<=cnt; i++){for(int j=1; j<=cnt; j++){c[i][j]=Min(a[i][k]+b[k][j],c[i][j]);}}} } void copy(int n,int a[][N],int b[][N]) {for(int i=0; i<=n; i++)for(int j=0; j<=n; j++)a[i][j]=b[i][j],b[i][j]=INF; } int solve(int s,int t,int n,int cnt) {while(n){if(n&1){floyed(ans,a,temp,cnt);copy(cnt,ans,temp);}floyed(a,a,temp,cnt);copy(cnt,a,temp);n>>=1;}return ans[s][t]; } int main() {int n,t,S,E;scanf("%d%d%d%d",&n,&t,&S,&E);int u,v,w;int cnt=0;mem(ans,0x3f);mem(temp,0x3f);mem(a,0x3f);for(int i=0; i<t; i++){scanf("%d%d%d",&w,&u,&v);if(!used[u]){used[u]=1;p[u]=++cnt;a[cnt][cnt]=temp[cnt][cnt]=ans[cnt][cnt]=0;}if(!used[v]){used[v]=1;p[v]=++cnt;a[cnt][cnt]=temp[cnt][cnt]=ans[cnt][cnt]=0;}a[p[u]][p[v]]=a[p[v]][p[u]]=w;}printf("%d\n",solve(p[S],p[E],n,cnt));return 0; }

這個題的邊不連續，要先離散化。

總結

以上是生活随笔為你收集整理的疯子的算法总结(九) 图论中的矩阵应用 Part 1 POJ3613 Cow Relays的全部內容，希望文章能夠幫你解決所遇到的問題。

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