「CodeForces 553E」Kyoya and Train

发表于 |
字数统计: 1.5k | 阅读时长 ≈ 7

为了表述方便，以下所述$p_{i,k}$均为原题中的$\frac{p_{i,k}}{100000}$

给定一个$n$个点$m$条边有向图，第$i$条边有边权$c_i$，可能的花费时间为$[1,t]$，且花费$k$时间的概率是$p_{i,k}$。

一个人从$1$到$n$，如果到达时间超过$T$，则需要额外缴纳$X$的花费，求期望最小花费。

$\texttt{Data Range:}2\leq n\leq 50,1\leq m\leq 100,1\leq t\leq 2\times 10^4,0\leq x,c_i\leq 10^6$

链接

Luogu

vjudge

题解

在你谷 AC 的第$1111$道题目，并且在凌晨之前做完了，写篇题解纪念一下呢qwq。

神仙们都是从上往下做的，只有我一个菜鸡从下往上，而且$\texttt{CF1184A3}$还被题意杀了。

第一次做$\texttt{3300}$的题目呢，而且还是$\texttt{myy}$的论文题，还是比较难的。

还是祝我能上$\texttt{Expert}$吧qwq

一道分治$\texttt{FFT}$好题。（但是这还是无法掩盖自己第一次写分治$\texttt{FFT}$的现实）

众所周知我们可以先$\texttt{dp}$，设$dp_{i,j}$表示到达$i$的时间为$j$的最小花费，$P_{e,t}$为走边$e$花费时间$t$的概率。对于某一个点$x$，枚举它的出边$e_i=(x,y_i)$，于是我们可以写出转移为

为什么这个转移成立呢？我们考虑把图看成一个以时间为层数的分层图，题目保证了一个点再也不能回到它的祖先（除非经过时间为负数），所以这张分成图是个$\texttt{DAG}$，就可以做了。

然后你会发现状态$O(mT)$，转移$O(T)$，嘿嘿，结果可想而知。

我们来设一个$g_{e,t}=c_e+\sum_{j=1}^{T}P_{e,j}dp_{y_e,t+j}$，再来设一个$f_{e,T+t}=g_{e,T}$，于是我们有

考虑翻转$P$，假设得到$Q$，则

噫，成了！出现卷积形式，但是这样过不了，因为右边与时间有关，怎么办呢？

于是我们可以对时间分治。

这里给一个恒等式

说白了，就是拆开，然后我们就可以高高兴兴上分治$\texttt{FFT}$了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
using namespace std;
typedef int ll;
typedef double db;
const ll MAXN=2e5+51;
const db PI=acos(-1.0);
struct Complex{
	db re,im;
	Complex(db x=0,db y=0)
	{
		this->re=x,this->im=y;
	}
};
struct Edge{
	ll from,to,dist;
};
Complex f[MAXN],g[MAXN];
Edge ed[MAXN];
ll nc,ec,t,x;
ll rev[MAXN];
db p[110][MAXN],dis[111][111],dp[111][40051],dp2[111][40051];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
} 
inline Complex operator +(Complex x,Complex y)
{
	return Complex(x.re+y.re,x.im+y.im);
}
inline Complex operator -(Complex x,Complex y)
{
	return Complex(x.re-y.re,x.im-y.im);
}
inline Complex operator *(Complex x,Complex y)
{
	return Complex(x.re*y.re-x.im*y.im,x.re*y.im+x.im*y.re);
}
inline Complex operator /(Complex x,db y)
{
	return Complex(x.re/y,x.im/y);
}
inline void FFT(Complex *cp,ll cnt,ll inv)
{
	ll cur=0;
	Complex res,omg;
	for(register int i=0;i<cnt;i++)
	{
		if(i<rev[i])
		{
			swap(cp[i],cp[rev[i]]);
		}
	}
	for(register int i=2;i<=cnt;i<<=1)
	{
		cur=i>>1,res=Complex(cos(2*PI/i),inv*sin(2*PI/i));
		for(register Complex *p=cp;p!=cp+cnt;p+=i)
		{
			omg=Complex(1,0);
			for(register int j=0;j<cur;j++)
			{
				Complex t=omg*p[j+cur],t2=p[j];
				p[j+cur]=t2-t,p[j]=t+t2;
				omg=omg*res;
			}
		}
	}
	if(inv==-1)
	{
		for(register int i=0;i<cnt;i++)
		{
			cp[i]=cp[i]/cnt;
		}
	}
}
inline void calc(ll l,ll r)
{
	ll mid=(l+r)>>1,cnt,limit;
	for(register int j=1;j<=ec;j++)
	{
		cnt=1,limit=-1;
		while(cnt<=((r<<1)-l-mid-1))
		{
			cnt<<=1,limit++;
		}
		for(register int i=0;i<cnt;i++)
		{
			rev[i]=(rev[i>>1]>>1)|((i&1)<<limit);
			f[i]=g[i]=Complex(0,0);
		}
		for(register int i=mid+1;i<=r;i++)
		{
			f[i-mid-1].re+=dp[ed[j].to][i];
		}
		for(register int i=1;i<=r-l;i++)
		{
			g[r-l-i].re+=p[j][i];
		}
		FFT(f,cnt,1),FFT(g,cnt,1);
		for(register int i=0;i<cnt;i++)
		{
			f[i]=f[i]*g[i];
		}
		FFT(f,cnt,-1);
		for(register int i=l;i<=mid;i++)
		{
			dp2[j][i]+=f[i-mid-1+r-l].re;
		}
	}
}
inline void cdqFFT(ll l,ll r)
{ 
	if(l==r)
	{
		for(register int i=1;i<=ec;i++)
		{
			dp[ed[i].from][l]=min(dp[ed[i].from][l],dp2[i][l]+ed[i].dist);
		}
		return;
	}
	ll mid=(l+r)>>1;
	cdqFFT(mid+1,r),calc(l,r),cdqFFT(l,mid);
}
int main()
{
	nc=read(),ec=read(),t=read(),x=read();
	for(register int i=1;i<=nc;i++)
	{
		for(register int j=1;j<=nc;j++)
		{
			dis[i][j]=i^j?1061109567.0:0;
		}
	}
	for(register int i=1;i<=ec;i++)
	{
		ed[i].from=read(),ed[i].to=read(),ed[i].dist=read();
		dis[ed[i].from][ed[i].to]=min(dis[ed[i].from][ed[i].to],1.0*ed[i].dist);
		for(register int j=1;j<=t;j++)
		{
			p[i][j]=read()/100000.0;
		}
	}
	for(register int k=1;k<=nc;k++)
	{
		for(register int i=1;i<=nc;i++)
		{
			for(register int j=1;j<=nc;j++)
			{
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	for(register int i=0;i<=(t<<1);i++)
	{
		dp[nc][i]=i<=t?0:x;
	}
	for(register int i=1;i<nc;i++)
	{
		for(register int j=0;j<=(t<<1);j++)
		{
			dp[i][j]=(j<=t)?0x3f3f3f3f:dis[i][nc]+x; 
		}
	}
	calc(1,t<<1),cdqFFT(0,t);
	printf("%.10lf\n",dp[1][0]);
}