【BZOJ-4386】Wycieczki DP + 矩阵乘法

4386: [POI2015]Wycieczki

Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 197 Solved: 49
[Submit][Status][Discuss]

Description

给定一张n个点m条边的带权有向图，每条边的边权只可能是1，2，3中的一种。
将所有可能的路径按路径长度排序，请输出第k小的路径的长度，注意路径不一定是简单路径，即可以重复走同一个点。

Input

第一行包含三个整数n,m,k(1<=n<=40，1<=m<=1000，1<=k<=10^18)。
接下来m行，每行三个整数u,v,c(1<=u,v<=n，u不等于v，1<=c<=3)，表示从u出发有一条到v的单向边，边长为c。
可能有重边。

Output

包含一行一个正整数，即第k短的路径的长度，如果不存在，输出-1。

Sample Input

6 6 11
1 2 1
2 3 2
3 4 2
4 5 1
5 3 1
4 6 3

Sample Output

HINT

长度为1的路径有1->2，5->3，4->5。
长度为2的路径有2->3，3->4，4->5->3。
长度为3的路径有4->6，1->2->3，3->4->5，5->3->4。
长度为4的路径有5->3->4->5。

Source

鸣谢Claris

Solution

边权只有1，2，3三种，可以考虑拆点，那么只有边权为1的边了

那么显然可以DP，但是时间复杂度不允许

考虑用矩阵乘法去转移

这里比较优秀的方法是基于倍增的矩阵乘法

总复杂度是$O(n^{3}logK)$

答案会很大，乘爆longlong需要特判

这题细节非常多！

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

inline long long read()

{

    long long x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define MAXN 130

int id[MAXN][],ID,N,M,B;

long long K,V[MAXN*];

struct MatrixNode{long long a[MAXN][MAXN];}a[],b,c,tmp;

MatrixNode operator * (const MatrixNode &A,const MatrixNode &B)

{

    MatrixNode C; memset(C.a,,sizeof(C.a));

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

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

                for (int k=; k<=ID; k++)

                    if (A.a[i][k]&&B.a[k][j])

                        {

                            if (A.a[i][k]< || B.a[k][j]<)  {C.a[i][j]=-; break;}

                            if (A.a[i][k]>K/B.a[k][j]) {C.a[i][j]=-; break;}

                            C.a[i][j]+=A.a[i][k]*B.a[k][j];

                            if (C.a[i][j]>K) {C.a[i][j]=-; break;}

                        }

    return C;

}

bool Check()

{

    long long re=;

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

        if (tmp.a[][i] && V[i])

            {

                if (tmp.a[][i]<) return ;

                if (tmp.a[][i]>K/V[i]) return ;

                re+=tmp.a[][i]*V[i];

                if (re>K) return ;

            }

    return re<K;

}

int main()

{

    N=read(),M=read(),K=read();

    for (int i=; i<=N; i++) for (int j=; j<=; j++) id[i][j]=++ID;

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

        {

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

                a[].a[id[i][j]][id[i][j+]]++;

            a[].a[][id[i][]]++;

        }

    a[].a[][]++;

    for (int x,y,z,i=; i<=M; i++) x=read(),y=read(),z=read(),a[].a[id[y][z-]][id[x][]]++,V[id[y][z-]]++;

    for (int i=; (1LL<<i)<=K*; B=++i); B--;

    for (int i=; i<=B; i++) a[i]=a[i-]*a[i-];

    long long ans=;

    for (int i=; i<=ID; i++) c.a[i][i]=;

    for (int i=B; ~i; i--)

        {

            tmp=c*a[i];

            if (Check()) ans|=(1LL<<i),memcpy(c.a,tmp.a,sizeof(tmp.a));

        }

    ans++;

    if (ans>K*) {puts("-1"); return ;}

        else printf("%lld\n",ans);

    return ;

}

模拟赛的时候，没认真读题，以为是“魔法猪学院”类似的...等到半场才发现.....然后GG

秒客网