「题解」：[线性代数]：relays 奶牛接力跑

问题: relays 奶牛接力跑

时间限制: 1 Sec 内存限制: 256 MB

题面

题目描述

FJ的N(2 <= N <= 1,000,000)头奶牛选择了接力跑作为她们的日常锻炼项目。至于进行接力跑的地点自然是在牧场中现有的T(2 <= T <= 100)条跑道上。农场上的跑道有一些交汇点，每条跑道都连结了两个不同的交汇点 I1_i和I2_i(1 <= I1_i <= 1,000; 1 <= I2_i <= 1,000)。每个交汇点都是至少两条跑道的端点。奶牛们知道每条跑道的长度length_i(1 <= length_i <= 1,000)，以及每条跑道连结的交汇点的编号并且，没有哪两个交汇点由两条不同的跑道直接相连。你可以认为这些交汇点和跑道构成了一张图。为了完成一场接力跑，所有N头奶牛在跑步开始之前都要站在某个交汇点上（有些交汇点上可能站着不只1头奶牛）。当然，她们的站位要保证她们能够将接力棒顺次传递，并且最后持棒的奶牛要停在预设的终点。你的任务是，写一个程序，计算在接力跑的起点(S)和终点(E)确定的情况下，奶牛们跑步路径可能的最小总长度。显然，这条路径必须恰好经过N条跑道。

输入格式

第1行: 4个用空格隔开的整数：N，T，S，以及E
第2..T+1行: 第i+1为3个以空格隔开的整数：length_i，I1_i，以及I2_i，描述了第i条跑道。

输出格式

第1行: 输出1个正整数，表示起点为S、终点为E，并且恰好经过N条跑道的路径的最小长度

样例输入

2 6 6 4

11 4 6

4 4 8

8 4 9

6 6 8

2 6 9

3 8 9

样例输出

题解

这道题是拓展矩阵乘法的入门题，也可以说是倍增Floyed。（同时也是我的第一道线性代数提高题）

本文主要从矩阵乘法角度入手。（因为说是倍增Floyed有点牵强，倍增主要体现在矩阵快速幂上）

我们都知道，使用矩阵快速幂的目的在于降低运算次数，以达到降低时间复杂度的效果。

矩阵乘法的运算代码如下：

Mal Mal_MULTI(Mal a,Mal b)
{
    Mal ans;
    for(int i=1;i<=cnt;++i)
        for(int j=1;j<=cnt;++j)
            for(int k=1;k<=cnt;++k)
                ans.data[i][j]=a.data[i][k]*b.data[k][j]
    return ans;
}

十分基础的矩阵乘法。

然而本题和它不同。本题要求的是求路径长度。所以显然不是各项相乘，而应该是相加。

但是相加显然不能满足题意要求的：最小路径。

所以我们需要取min。

于是矩阵乘法的函数就变成了这个样子：

Mal Mal_MULTI(Mal a,Mal b)
{
    Mal ans;
    memset(ans.data,0x3f,sizeof(ans.data));
    for(rint i=1;i<=cnt;++i)
        for(rint j=1;j<=cnt;++j)
            for(rint k=1;k<=cnt;++k)
                ans.data[i][j]=min(ans.data[i][j],a.data[i][k]+b.data[k][j]);
    return ans;
}

相信大家都看出来了，这显然与floyed十分相似。所以我们也称他倍增优化的Floyed算法。

然而这样求不是个事啊QAQ，N大的吓人，1e6，所以我们又搬出了矩阵快速幂。

别忘了开离散化哦～

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<stack>
#include<cmath>
#define rint register int
using namespace std;
int in_n,in_t,in_s,in_e,ls_dy[1000006],in_x,in_y;
int cnt,in_l;
struct Mal{int data[103][103],line;}map,anss;
Mal Mal_MULTI(Mal a,Mal b)
{
    Mal ans;
    memset(ans.data,0x3f,sizeof(ans.data));
    for(rint i=1;i<=cnt;++i)
        for(rint j=1;j<=cnt;++j)
            for(rint k=1;k<=cnt;++k)
                ans.data[i][j]=min(ans.data[i][j],a.data[i][k]+b.data[k][j]);
    return ans;
}
Mal Mal_QPOW(Mal a,int x)
{
    Mal ans;
    memset(ans.data,0x3f,sizeof(ans.data));
    for(rint i=1;i<=cnt;++i)
        ans.data[i][i]=0;
    while(x)
    {
        if(x&1)ans=Mal_MULTI(ans,a);
        a=Mal_MULTI(a,a);x>>=1;
    }
    return ans;
}
int main()
{
    memset(anss.data,0x3f,sizeof(anss.data));
    memset(map.data,0x3f,sizeof(map.data));
//    cout<<map.data[1][1]<<endl;
    scanf("%d %d %d %d",&in_n,&in_t,&in_s,&in_e);
    for(rint i=1;i<=in_t;++i)
    {
        scanf("%d %d %d",&in_l,&in_x,&in_y);
        if(!ls_dy[in_x])ls_dy[in_x]=++cnt;
        if(!ls_dy[in_y])ls_dy[in_y]=++cnt;
        map.data[ls_dy[in_x]][ls_dy[in_y]]=in_l;
        map.data[ls_dy[in_y]][ls_dy[in_x]]=in_l;
    }
    for(rint i=1;i<=cnt;++i) anss.data[i][i]=0;
    for(rint i=1;i<=cnt;++i,cout<<endl)
        for(rint j=1;j<=cnt;++j)
            cout<<anss.data[i][j]<<' ';
    cout<<endl<<endl;
    for(rint i=1;i<=cnt;++i,cout<<endl)
        for(rint j=1;j<=cnt;++j)
            cout<<map.data[i][j]<<' ';
    cout<<endl<<endl;
    anss=Mal_MULTI(anss,map);
    for(rint i=1;i<=cnt;++i,cout<<endl)
        for(rint j=1;j<=cnt;++j)
            cout<<anss.data[i][j]<<' ';
    return 0;
}

View Code