问题描述
Ralph打算去蘑菇森林采蘑菇。
蘑菇森林里有n个蘑菇丛，有m条有向的路连接这些丛林（可能连向自己，也可能两个丛林之间有多条路）。经过某条路时，Ralph可以采走这条路上的全部蘑菇。然而，这是一片神奇的蘑菇森林，蘑菇被采走后会重新长出来一些。但是，第k次走过这条路后，这条路上重新长出的蘑菇会比上次少k。（举个栗子，第一次有w个蘑菇，第二次有w-1个蘑菇，第三次有w-1-2个蘑菇，以此类推……）（还有，蘑菇的数量大于0）。
那么，Ralph最多可以采到多少蘑菇呢？
输入格式
第一行两个数n,m。
第2~m+1行，每行三个数u，v，w，表示u到v有一条道路，上面有w个蘑菇。
最后一行一个数s，表示起点。
输出格式
一个数，表示最多能采多少蘑菇。
样例输入
2 2
1 2 4
2 1 4
1
样例输出
16
解析
既然边可以经过任意次数，那么可以想到，一个强联通分量中的所有边上的蘑菇我们一定可以采到小于等于0为止(绕着这个环走即可)。所以首先Tarjan缩点，对于不在强联通分量中的点，只能经过一次。接下来的问题就是如何计算一个环上的最大收益。
计算环的收益可以转化为计算每一条边的收益。设边的权值为w，经过的次数k一定是满足((k+1)*k/2<=w)的最大的k，可以用二分求解。那么，一条边的收益为
[w+(w-1)+(w-1-2)+...+(w-1-2-...-k)
]
也就是
[(k+1)*w-sum_{i=1}^{k}i*(i+1)/2
]
前缀和处理即可。在缩点后的DAG上动态规划得到最终答案。
代码
#include <iostream>
#include <cstdio>
#define int long long
#define N 1000002
using namespace std;
int head[N],ver[N],nxt[N],edge[N],l;
int head1[N],ver1[N],nxt1[N],edge1[N],l1;
int n,m,S,i,j,tim,dfn[N],low[N],top,s[N],cnt,scc[N],w[N],sum[N],f[N];
int read()
{
char c=getchar();
int w=0;
while(c<'0'||c>'9') c=getchar();
while(c<='9'&&c>='0'){
w=w*10+c-'0';
c=getchar();
}
return w;
}
void insert(int x,int y,int z)
{
l++;
ver[l]=y;
edge[l]=z;
nxt[l]=head[x];
head[x]=l;
}
void insert1(int x,int y,int z)
{
l1++;
ver1[l1]=y;
edge1[l1]=z;
nxt1[l1]=head1[x];
head1[x]=l1;
}
void Tarjan(int x)
{
dfn[x]=low[x]=++tim;
s[++top]=x;
for(int i=head[x];i;i=nxt[i]){
int y=ver[i];
if(!dfn[y]){
Tarjan(y);
low[x]=min(low[x],low[y]);
}
else if(!scc[y]) low[x]=min(low[x],dfn[y]);
}
if(dfn[x]==low[x]){
cnt++;
while(1){
int y=s[top--];
scc[y]=cnt;
if(x==y) break;
}
}
}
int cal(int x)
{
int l=0,r=100000,mid,k;
while(l<=r){
mid=(l+r)/2;
if(mid*(mid+1)/2<=x){
k=mid;
l=mid+1;
}
else r=mid-1;
}
return (k+1)*x-sum[k];
}
int dfs(int x)
{
if(f[x]) return f[x];
f[x]=w[x];
for(int i=head1[x];i;i=nxt1[i]){
int y=ver1[i];
f[x]=max(f[x],w[x]+dfs(y)+edge1[i]);
}
return f[x];
}
signed main()
{
for(i=1,j=1;i<=100000;i++,j+=i) sum[i]=sum[i-1]+j;
n=read();m=read();
for(i=1;i<=m;i++){
int u=read(),v=read(),w=read();
insert(u,v,w);
}
S=read();
for(i=1;i<=n;i++){
if(!dfn[i]) Tarjan(i);
}
for(i=1;i<=n;i++){
for(j=head[i];j;j=nxt[j]){
if(scc[i]==scc[ver[j]]) w[scc[i]]+=cal(edge[j]);
else insert1(scc[i],scc[ver[j]],edge[j]);
}
}
cout<<dfs(scc[S])<<endl;
return 0;
}