自动搬运

查看原文

来自洛谷，原作者为

	木xx木大 已经 AFO 的菜鸡 OIer

搬运于2025-08-24 21:50:34，当前版本为作者最后更新于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$ 的方案数之和。

$k$ 太大，如果一个一个乘，复杂度不对；于是我们倍增优化即可。倍增这块其他题解写得很清楚，这里就不再赘述了。

#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;
}