矩阵乘法/最长路

\(NOI2020\)唯一在蒟蒻能力范围之内的题目没有\(A\)掉,\(QAQ\)

考试的时候一看数据范围，矩阵快速幂！一直在考虑拆边,结果发现点数高达\(2500+\),然后一直考虑不拆边怎么转移(分类讨论之类的),然后就咕咕了。

实际上可以拆点呀，这样就只有\(50 \times 5=250\)个点了(草率啊)

由于我们只需要求\(1 \rightarrow \cdots \rightarrow 1\)的路径,而且我们需要在\(t_i\)时间到达的位置\(+y_i\),我们就只存一行就好了

预处理出初始矩阵的\(2^{\lceil log_{2} T \rceil}\)次幂,跑\(200\)次矩阵快速幂,就轻松地\(AC\)了?(~~菜死了~~)

#include<iostream>
#include<cstdio>
#include<algorithm>
#define INF 12345678987654321
#define ll long long
#define N 255
using namespace std;
int n,m,T,k,cnt,tot,x,y,z,l;
int xfkz[N],kz[N][6];
struct ques
{
    int t,x,y;
}q[N];
bool operator < (ques A,ques B)
{
    return A.t<B.t;
}
struct mat
{
    int R,C;
    ll a[N][N];
}f,zlkz[32],ans;
mat operator * (mat e,mat f)
{
    mat c;
    c.R=e.R;
    c.C=f.C;
    for (int i=1;i<=c.R;i++)
        for (int j=1;j<=c.C;j++)
            c.a[i][j]=-INF;
    for (int k=1;k<=e.C;k++)
        for (int i=1;i<=c.R;i++)
            for (int j=1;j<=c.C;j++)
                c.a[i][j]=max(c.a[i][j],e.a[i][k]+f.a[k][j]);
    return c;
}
void kzhmcf(int x)
{
    for (int i=0;i<=l;i++)
        if (x & (1 << i))
            ans=ans*zlkz[i];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&T,&k);
    for (int i=1;i<=n;i++)
        scanf("%d",&xfkz[i]);
    tot=n*5;
    f.R=f.C=tot;
    for (int i=1;i<=tot;i++)
        for (int j=1;j<=tot;j++)
            f.a[i][j]=-INF;
    cnt=n;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=5;j++)
        {
            kz[i][j]=(j==1)?i:(++cnt);
            f.a[kz[i][j-1]][kz[i][j]]=0;
        }
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        f.a[kz[x][z]][y]=xfkz[y];
    }
    zlkz[0]=f;
    int s=1;
    l=0;
    while (s<T)
    {
        s <<=1;
        l++;
        zlkz[l]=zlkz[l-1]*zlkz[l-1];
    }
    ans.R=1,ans.C=tot;
    for (int i=1;i<=tot;i++)
        ans.a[1][i]=(i==1)?0:-INF;
    for (int i=1;i<=k;i++)
        scanf("%d%d%d",&q[i].t,&q[i].x,&q[i].y);
    sort(q+1,q+k+1);
    int pre=0;
    for (int i=1;i<=k;i++)
    {
        kzhmcf(q[i].t-pre);
        ans.a[1][q[i].x]+=q[i].y;
        pre=q[i].t;
    }
    kzhmcf(T-pre);
    if (ans.a[1][1]<0)
        puts("-1"); else
        printf("%lld\n",ans.a[1][1]+xfkz[1]);
    return 0;
}

Luogu6772 [NOI2020]美食家

矩阵乘法/最长路

推荐阅读