P3597 [POI2015]WYC（矩阵乘法+倍增）
木xx木大
·
2020-12-03 17:50:06
·
题解
P3597 [POI2015]WYC
首先，发现点数和边权都很小，于是我们按照套路拆点+矩乘：把一个点拆成 u_1,u_2,u_3 ，连边 u_3\rightarrow u_2,u_2\rightarrow u_1 ，对于一条给定的边 (u,v,w) ，连边 (u_1,v_w) 。
如果直接求这个转移矩阵的 d 次方，那么求出的矩阵中的值 (u_1,v_1) 表示 u\rightarrow v 走过的路径长恰好为 d 的方案数。 为了方便判断，我们需要求出路径长 \le d 的方案数之和。那么我们建一个超级汇点0 ，连边 (u_1,0) ，超级汇点处的方案数就是全局的方案数。为了保留上一次得到的答案，我们再连边 (0,0) 。 这样， (0,0) 处的值就是路径长 \le d 的方案数之和。
```cpp
#include<bits/stdc++.h>
#define ld long double
#define ll long long
using namespace std;
namespace FGF
{
int n,m;
ll K,ans;
struct matrx{
ld a[130][130];
}g[110],A;
matrx operator *(matrx x,matrx y)
{
matrx s;memset(s.a,0,sizeof(s.a));
for(int i=0;i<=3*n;i++)
for(int j=0;j<=3*n;j++)
for(int k=0;k<=3*n;k++)
s.a[i][j]+=x.a[i][k]*y.a[k][j];
return s;
}
void work()
{
scanf("%d%d%lld",&n,&m,&K);
for(int i=1;i<=n;i++)
A.a[0][(i-1)*3+1]=g[0].a[(i-1)*3+1][0]=g[0].a[(i-1)*3+2][(i-1)*3+1]=g[0].a[(i-1)*3+3][(i-1)*3+2]=1;
g[0].a[0][0]=1;
for(int i=1;i<=m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[0].a[(u-1)*3+1][(v-1)*3+w]++;
}
int d;
for(d=1;;d++)
{
g[d]=g[d-1]*g[d-1];
matrx tmp=A*g[d];
if(tmp.a[0][0]-n>=K)break;
if(d>=64)
{
puts("-1");
return;
}
}
for(;d>=0;d--)
{
matrx tmp=A*g[d];
if(tmp.a[0][0]-n<K)A=tmp,ans+=(1LL<<d);
}
printf("%lld",ans);
}
}
int main()
{
FGF::work();
return 0;
}
```