poj3613Cow Relays 矩阵快速幂

59 阅读 0 评论 39 点赞

我是靠谱客的博主迷人乌冬面，最近开发中收集的这篇文章主要介绍poj3613Cow Relays 矩阵快速幂，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

矩阵+快速幂。用矩阵做floyd。

由于一定要走K步，如果用dp[][]来表示的话就是，dp[i][ed]=min(dp[i][ed],dp[i][j]+val[j->ed]);

由于原图不会改变，所以dp[i]和dp[i-1]更新效果也是一定的，所以我们可以用快速幂来降低图的遍历次数。

然后快速幂的“1”矩阵与常规的不一样，由于“1”矩阵的作用是让所有矩阵乘以它后值不变，本题中矩阵乘法的定义有所改变，所以不能定义为只有对角线上都是1的普通“1”矩阵。假设极端情况，如果只走一步的话那么就应该是原图，

为了不改变原图，所以“1”矩阵的对角线应该为0 其他值为INF。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
map<int,int>mmap;
int n;
struct matrix
{
    int a[110][110];
}org,res,tmp;
matrix operator * (matrix x,matrix y)
{
    matrix c;
    memset(c.a,0x3f3f3f3f,sizeof(c.a));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                c.a[i][j]=min(c.a[i][j],x.a[i][k]+y.a[k][j]);
            }
        }
    }
    return c;
}
matrix solve(matrix A,int k)
{
    memset(res.a,0x3f3f3f3f,sizeof (res.a));
    for(int i=1;i<=n;i++)
        res.a[i][i]=0;
    while(k)
    {
        if(k&1)res=res*A;
        A=A*A;
        k>>=1;
    }
    return res;
}
int main()
{
    int k,m,s,e;
    int x,y,z;
    while(~scanf("%d%d%d%d",&k,&m,&s,&e))
    {
    memset(org.a,0x3f3f3f3f,sizeof(org.a));
    mmap.clear();
    int num=0;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&z,&x,&y);
        if(!mmap[x])
            mmap[x]=++num;
        if(!mmap[y])
            mmap[y]=++num;
        int l=mmap[x];
        int r=mmap[y];
        org.a[l][r]=org.a[r][l]=z;
    }
    n=num;
    matrix ans=solve(org,k);
    printf("%dn",ans.a[mmap[s]][mmap[e]]);
    }
    return 0;
}