POJ --- 3613 (K步最短路+矩阵快速幂+floyd)

时间：2022-03-10 19:27:24
Cow Relays
 

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

题意：在无向图中有n条边，现在给出你一个起点S和一个终点E，让你求从S到E经过且仅K条边的最短路径。注意此题中K远大于n，如果K小于n的话直接一边广搜就过了，第一次没注意到这个条件敲了一个BFS，结果WA了。

思路：此题正解应该是矩阵乘法，但是重定义了，区别于线性代数里面的乘法（其实可以看出无论哪种定义，只要能推出矩阵在该定义下满足交换律即可，因为可以用快速幂来加速）。
设原图G对应的邻接矩阵为M，则M的k次幂中M[i][j]就表示从i点到j点经过k条边路径的个数！那么只需要重新定义一下矩阵乘法：M[i][j]表示从i点到j点的的最短路径长度，即M[i][j] = min(M[i][j],M[i][k]+M[k][j])(这个就是floyd算法的核心，DP思想)，可以证明该定义满足交换律，因此可以用快速幂，考虑M^2,它表示从i到j经过2条边的最短路径，同理推出M^n表示从i到j经过n条边的最短路径，因此本题得解。
关于矩阵乘法的应用是参考2008年国家集训队论文《矩阵乘法在信息学中的应用》（俞华程）中看到的，网上此题解法大都参考该论文，在网上看了别人解释的没怎么看懂，直接看论文去了，发现论文里面讲的很明白也很透彻，但是经过别人转述意思可能就不一样了，其实我也说的不怎么清楚，所以建议直接去看论文。
网盘下载地址：http://yunpan.cn/QNeFIw2wIef4B （访问密码：7b0c）


 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define MAXN 111

 using namespace std;

 class Matrix{

     public:

         int m[MAXN][MAXN];

         Matrix(){

             memset(m, -, sizeof(m));

         }

 };

 int N = ;

 Matrix mtMul(Matrix A, Matrix B){

     Matrix tmp;

     for(int i = ;i < N;i ++)

         for(int j = ;j < N;j ++)

             for(int k = ;k < N;k ++){

                 if(A.m[i][k] == - || B.m[k][j] == -) continue;

                 int temp = A.m[i][k] + B.m[k][j];

                 if(tmp.m[i][j] == - || tmp.m[i][j] > temp) tmp.m[i][j] = temp;

             }

     return tmp;

 }

 Matrix mtPow(Matrix A, int k){

     if(k == ) return A;

     Matrix tmp = mtPow(A,  k >> );

     Matrix res = mtMul(tmp, tmp);

     if(k & ) res = mtMul(res, A);

     return res;

 }

 int main(){

     int cnt[];

     int n, t, s, e;

     int u, v, w;

     /* freopen("in.c", "r", stdin); */

     while(~scanf("%d%d%d%d", &n, &t, &s, &e)){

         N = ;

         Matrix G;

         memset(cnt, -, sizeof(cnt));

         for(int i = ;i < t;i ++){

             scanf("%d%d%d", &w, &u, &v);

             if(cnt[u] == -) cnt[u] = N++;

             if(cnt[v] == -) cnt[v] = N++;

             G.m[cnt[u]][cnt[v]] = w;

             G.m[cnt[v]][cnt[u]] = w;

         }

         Matrix tmp = mtPow(G, n);

         printf("%d\n",tmp.m[cnt[s]][cnt[e]]);

     }

     return ;

 }
另外附上BFS的错误代码：
 #include<queue>

 #include<cstdio>

 #include<string>

 #include<cstring>

 #include<algorithm>

 #define MAXN 1111

 using namespace std;

 class Status{

     public:

         int pre, w, cnt;

         bool operator < (const Status &a) const{

             return w < a.w;

         }

 };

 typedef struct{

     int to, next, w;

 }Edge;

 Edge edge[];

 priority_queue<Status>q;

 int head[MAXN], N, T, S, E;

 void addedge(int u, int v, int w, int k){

     edge[k].to = v;

     edge[k].next = head[u];

     edge[k].w = w;

     head[u] = k++;

     edge[k].to = u;

     edge[k].next = head[v];

     edge[k].w = w;

     head[v] = k;

 }

 void bfs(int s){

     while(!q.empty()) q.pop();

     Status tmp;

     tmp.pre = s;

     tmp.w = tmp.cnt = ;

     q.push(tmp);

     while(!q.empty()){

         Status p = q.top();

         int v = p.pre;

         q.pop();

         for(int i = head[v]; ~i; i = edge[i].next){

             int u = edge[i].to;

             if(u == E && p.cnt+ == N){

                 printf("%d\n", p.w+edge[i].w);

                 return;

             }else if(u != E){

                 Status t;

                 t.pre = u;

                 t.w = p.w+edge[i].w;

                 t.cnt = p.cnt+;

                 q.push(t);

             }

         }

     }

 }

 int main(){

     int length, u, v, k;

     /* freopen("in.c", "r", stdin); */

     while(~scanf("%d%d%d%d", &N, &T, &S, &E)){

         memset(head, -, sizeof(head));

         k = ;

         for(int i = ; i < T; i ++){

             scanf("%d%d%d", &length, &u, &v);

             addedge(u, v, length, k);

             k += ;

         }

         bfs(S);

     }

     return ;

 }


 
相关文章