题解 CF894E 【Ralph and Mushrooms】
Hexarhy
2021-01-08 22:12:09
### Preface
远古 CF 图论板子题，套了个数学。
### Solution
不难想到，在有向图中，环上的边可以一直遍历直到取完。其余的边只能走一次。
因此可以考虑缩点，在 DAG 上拓扑求出答案。
关键在于如何计算环上的点可以得到多少贡献。
考虑一条边，权值为 $w$，有效经过次数为 $t$，那么满足：
$$\frac{t(t+1)}{2}\le w$$
解一下二次不等式，可以得到：
$$t=\lceil\dfrac{\sqrt{1+8w}-1}{2} \rceil$$
然后就是计算这 $t$ 次经过能产生的总贡献：
$$w+(w-1)+(w-1-2)+\cdots +(w-1-2-\cdots -(t-1))$$
写成和式就是（**考虑每个数字减去的次数**）：
$$tw-\sum_{i=0}^{t-1} (t-i)i$$
把 $\sum$ 里的拆开，最后得到：
$$tw-\left(\frac{t^2(t-1)}{2}-\frac{t(t-1)(2t-1)}{6}\right)$$
----------
接下来是图论部分。
缩点之后这个环上的权值加在这个缩成点上，然后拓扑排序 +dp 就行了，很套路。dp 写出来就是：
$$f_v=\max\{f_{u}+w_v+val(u,v)\}$$
其中 $w_v$ 是 $v$ 这个点缩点后的点权，$val(u,v)$ 是 $u\to v$ 的边权。
### Code
笔者的缩点是并查集实现的，有很多细节。这里不便悉数指出。
```cpp
int find(cint& a)
{
return f[a]==a?a:f[a]=find(f[a]);
}
inline ll calc(const ll n)
{
const ll t=ceil((sqrt(1+8ll*n)-1.0)/2.0);
const ll p=(t-1)*t*t/2-(t-1)*t*(2*t-1)/6;
return t*n-p;
}
void dfs(cint& u)
{
for(const auto& it:edge[u])
{
cint& v=it.to;
if(!visit[v])
{
visit[v]=visit[u]+1;
dfs(v);
}
cint fu=find(u),fv=find(v);
if(visit[fv]>0)
{
if(visit[fu]<visit[fv]) f[fv]=fu;
else f[fu]=fv;
}
}
visit[u]=-1;
}
void topo_sort(void)
{
for(int i=1;i<=n;i++)
dis[find(i)]=w[find(i)];
queue <int> q;
for(int i=1;i<=n;i++)
if(!indeg[i])
q.emplace(i);
memset(visit,0,sizeof(visit));
while(!q.empty())
{
cint u=q.front();q.pop();
if(visit[u]) continue;
visit[u]=true;
for(const auto& it:edge[u])
{
cint v=it.to;
dis[v]=max(dis[v],dis[u]+it.val+w[v]);
indeg[v]--;
if(!indeg[v]) q.emplace(v);
}
}
}
int main()
{
read(n,m);
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
int u,v,val;read(u,v,val);
e[i]=Edge{u,v,val};
edge[u].emplace_back(node{v,val});
}
read(st);
for(int i=1;i<=n;i++)
if(!visit[i])
{
visit[i]=1;
dfs(i);
}
for(int i=1;i<=n;i++) edge[i].clear();
for(int i=1;i<=m;i++)
{
cint x=find(e[i].u),y=find(e[i].v);
if(x==y) w[x]+=calc(e[i].w);
}
for(int i=1;i<=m;i++)
{
cint x=find(e[i].u),y=find(e[i].v);
if(x==y) continue;
edge[find(e[i].v)].emplace_back(node{find(e[i].u),e[i].w});
indeg[find(e[i].u)]++;
}
topo_sort();
cout<<dis[find(st)]<<endl;
return 0;
}
```