poj3613-floyd+邻接矩阵乘法

参考于：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：

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 ≤ I_1i ≤ 1,000; 1 ≤ I_2i ≤ 1,000), each of which is the termination for at least two trails. The cows know the length_i of each trail (1 ≤ length_i  ≤ 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: length_i , I_1i , and I_2i

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
#include#define min(x,y) (x>=1;}}}mf;int main()
{mf.in();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！