poj3613-floyd+邻接矩阵乘法

小灰灰 2022-07-12 04:51 160阅读 0赞

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

Cow Relays

<table> 
 <tbody> 
  <tr> 
   <td><strong>Time Limit:</strong>&nbsp;1000MS</td> 
   <td>&nbsp;</td> 
   <td><strong>Memory Limit:</strong>&nbsp;65536K</td> 
  </tr> 
  <tr> 
   <td><strong>Total Submissions:</strong>&nbsp;7357</td> 
   <td>&nbsp;</td> 
   <td><strong>Accepted:</strong>&nbsp;2887</td> 
  </tr> 
 </tbody> 
</table>

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*1*i* ≤ 1,000; 1 ≤ *I*2*i* ≤ 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* , *I*1*i* , and *I*2*i*

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

Source

[USACO 2007 November Gold][]

题目大意：

给定一张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;
    }

[USACO 2007 November Gold]: http://poj.org/searchproblem?field=source&key=USACO+2007+November+Gold