[文章目录]
Description
超级轨道包含 E (1 <= E <=150,000)条小轨道连接着V (V <= 50,000)个水池，编号为1..V。每个小轨道必须按照特定的方向运行，不能够反向运行。奶牛们从1号水池出发，经过若干条小轨道，最终到达V号水池。每个水池(除了V号和1号之外，都有至少一条小轨道进来和一条小轨道出去，并且，一头奶牛从任何一个水池到达V 号水池。最后，由于这是一个冲浪，从任何一个水池出发都不可能回到这个水池) 每条小轨道从水池P_i到水池Q_i (1 <= P_i <= V; 1<= Q_i <= V; P_i != Q_i)， 轨道有一个开心值F_i (0 <= F_i <= 2,000,000,000)，Bessie总的开心值就是经过的所有轨道的开心值之和。Bessie自然希望越开心越好，并且，她有足够长的时间在轨道上玩。因此，她精心地挑选路线。但是，由于她是头奶牛，所以，会有至多K (1 <= K <= 10)次的情况，她无法控制，并且随机从某个水池选择了一条轨道(这种情况甚至会在1号水池发生) 如果Bessie选择了在最坏情况下，最大化她的开心值，那么，她在这种情况下一次冲浪可以得到的最大开心值是多少？
显然dp。又由于这是一张DAG图，所以将拓扑序逆序搞出来然后dp就好了。设dp[i][j]表示i节点剩余j次飘逸机会至少的开心值。
dp[i][j]=min(max(dp[to[i][j]),min(dp[to[i]][j-1]));
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fll;
int n,m,tim;
int rd[50100];
int head[50100],to[151000],nxt[151000],f[151000],cnt;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
}
int ra[50100];
inline void topsort()
{
int tmp=n,now=n,x;
for(int i=1;i<=n;++i)
if(!rd[i]) ra[tmp--]=i;
while(tmp)
{
x=ra[now--];
for(int i=head[x];i;i=nxt[i])
{
rd[to[i]]--;
if(!rd[to[i]]) ra[tmp--]=to[i];
}
}
}
ll dp[12][51000];
int main()
{
scanf("%d%d%d",&n,&m,&tim);
for(int x,y,z,i=1;i<=m;++i)
{
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); rd[y]++;
}
topsort();
for(int i=1;i<=n;++i)
{
for(int j=head[ra[i]];j;j=nxt[j])
dp[0][ra[i]]=max(dp[0][ra[i]],dp[0][to[j]]+f[j]);
}
ll x,y;
for(int i=1;i<=tim;++i)
{
for(int j=1;j<=n;++j)
{
dp[i][ra[j]]=dp[i-1][ra[j]]; x=inf; y=-inf;
for(int k=head[ra[j]];k;k=nxt[k])
x=min(x,dp[i-1][to[k]]+f[k]),
y=max(y,dp[i][to[k]]+f[k]);
if(x!=inf) dp[i][ra[j]]=min(dp[i][ra[j]],min(x,y));
}
}
printf("%lld",dp[tim][1]);
return 0;
}