参考于：08年论文：俞华程《矩阵乘法在信息学中的应用》
图邻接矩阵上的乘法：
图的邻接矩阵可以唯一地表示一张图，并且有很多神奇的性质。接下来我们 将研究邻接矩阵上的矩阵乘法。
首先，我们来看一下最简单的情况，一张N个点的无向无权图。如果点a和 点b连边，那么邻接矩阵G[a,b] = G[b,a] = 1，否则都等于0。考虑邻接矩阵自 乘，即G2：
G2 [a,b] = N ∑ i=1 G[a,i]G[i,b] (9)
上式中，G[a,i],G[i,b]的值或者等于0或者等于1。易知当且仅当G[a,i], G[i,b]都是1的时候值为1，即如果从点a到点i、点i到b都有边，那么值为1。 而G2 [a,b]的值就等于值为1的项数，也就是从点a到点b经过1个中间点的路径条 数。我们继续考虑G3：
G3 [a,b] =N ∑ i=1N ∑ j=1G[a,i]G[i,j]G[j,b] (10)
和G2很相似，G[a,i]G[i,j]G[j,b] = 1当且仅当G[a,i] = G[i,j] = G[j,b] = 1，也就是说a−i−j−b组成一条路经。那么G3 [a,b]的值就是从点a到点b经过2个 中间点的路径条数。从另一个方面来说，G3 = G2G，从点a到点b经过2个中间 点的路径中，第二个中间点是i的路径条数恰好为G2 [a,i]G[i,b]，从这里也可 以说明上一个结论。那么更一般的，Gk [a,b]是否就等就a到b经过k −1个中间 点也就是长度为k的路径条数呢？答案是肯定的。和前面的推导很相似，可以 使用归纳法证明，Gk = Gk−1G，那么
Gk [a,b] =N ∑ i=1Gk−1 [a,i]G[i,b] (11)
其中Gk−1 [a,i]就是从a到i长度为k−1的路径条数，G[i,b]则表示了i到b是否 有路径，两者相乘恰好就是从a到b长度为k的路径上倒数第二个点为i的路径条 数。当k = 0时，G0为单位矩阵，G0 [a,a] = 1也符合a到a有一条长度为0的路 径。前面的证明当中并没有用到任何无向图的信息，因此这个结论也适用于有 向图。
那么对于有重边的图，我们只需要把G[a,b]改为表示点a,b之间重边的条 数即可。证明和前面的几乎一样，此处就不在赘述。而对于有向图的自环， 不需要特殊考虑。对于无向图的自环，我们通常是把G[a,a]加上2，这样在计 算Gk的时候这条边就被算成2条不同的边，如果只加上1，又会不满足矩阵里所 有元素和等于边数两倍的性质。需要怎样应具体情况具体分析。
poj3613：
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 7357 | Accepted: 2887 |
Description
For their physical fitness program, N (2 ≤ N ≤ 1,000,000) cows have decided to run a relay race using the T (2 ≤ T ≤ 100) cow trails throughout the pasture.
Each trail connects two different intersections (1 ≤ I1i ≤ 1,000; 1 ≤ I2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the lengthi of each trail (1 ≤ lengthi ≤ 1,000), the two intersections the trail connects, and they know that no two intersections are directly connected by two different trails. The trails form a structure known mathematically as a graph.
To run the relay, the N cows position themselves at various intersections (some intersections might have more than one cow). They must position themselves properly so that they can hand off the baton cow-by-cow and end up at the proper finishing place.
Write a program to help position the cows. Find the shortest path that connects the starting intersection (S) and the ending intersection (E) and traverses exactly N cow trails.
Input
* Line 1: Four space-separated integers: N, T, S, and E
* Lines 2..T+1: Line i+1 describes trail i with three space-separated integers: lengthi , I1i , and I2i
Output
* Line 1: A single integer that is the shortest distance from intersection S to intersection E that traverses exactly N cow trails.
Sample Input
2 6 6 4 11 4 6 4 4 8 8 4 9 6 6 8 2 6 9 3 8 9
Sample Output
10
Source
题目大意：
给定一张M条边的无向带权图，求从起点S到终点E恰好经过K条边的最短 路径。2≤ M ≤100,2≤ K ≤1000000。保证每个连边的点度至少为2。
题目思路：
有了前面矩阵乘法的概念，所以我们不妨设ans[i][j]^k表示为i->j经过k条边的最短路，而应为k很大，所以我们要用到矩阵快速幂，而对于题目给的点我们可以离散化下这样最大就只有100个点了，我们初始时用map[i][j]来保存地图，这里求矩阵的乘我们可以借用floyd，我们知道floyd的原理是更新以k为中间点的最短路，而我们的邻接矩阵的乘G[i][j]*G[i][j] 也就是找中间的k使得i->k和k->j
都有路而对于最短路矩阵乘我们可以在遍历k时取个最短的，也就是c[i][j]=min(a[i][k]+b[k][j],1<=k<=n)a,b为两个矩阵如果a是经过x条边b是经过y条边那么c就是经过x+y条边的最短路，这个很好想到，所以最后面我们只需将map跑k遍floyd就是答案，但是k太大，所以要二分矩阵也就是矩阵快速幂！
AC代码：
#include<cstring>
#include<cstdio>
#define min(x,y) (x<y?x:y)
const int inf = 0x3f3f3f3f;
class MatrixFloyd{
public:
int n,m,s,t,k;
int ans[205][205],tmp[205][205],mp[205][205],dis[205][205],v[1005];
void init(){
n=0;
memset(v,-1,sizeof(v));
for(int i=0;i<200;i++){
for(int j=0;j<200;j++)
ans[i][j]=tmp[i][j]=mp[i][j]=dis[i][j]=inf;
ans[i][i]=0;
}
}
void in(){
init();
scanf("%d%d%d%d",&k,&m,&s,&t);
while(m--){
int w,x,y;scanf("%d%d%d",&w,&x,&y);
if(v[x]==-1)v[x]=n++; //将点离散化
if(v[y]==-1)v[y]=n++;
mp[v[x]][v[y]]=mp[v[y]][v[x]]=min(mp[v[x]][v[y]],w);
}
sove();
printf("%d\n",ans[v[s]][v[t]]);
}
void floyd(int c[][205],int a[][205],int b[][205]){
for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
c[i][j]=min(c[i][j],a[i][k]+b[k][j]);
}
void sove(){
while(k){
if(k&1){ //二进制位为1
floyd(dis,ans,mp); //用dis保存ans和mp相乘的矩阵，即c=a+b
memcpy(ans,dis,sizeof(ans)); //赋值给ans
memset(dis,0x3f,sizeof(dis)); //在初始化dis
}
floyd(tmp,mp,mp);
memcpy(mp,tmp,sizeof(mp)); //mp表示的是mp^2^n n为二进制长度
memset(tmp,0x3f,sizeof(tmp));
k>>=1;
}
}
}mf;
int main()
{
mf.in();
return 0;
}
京公网安备 11010502036488号