[Codeforces Round #447][Codeforces 894E]Ralph and Mushrooms

    题意：给出一个有向图，对于一条边i，其初始权值为\(w_i\)，第一次经过该边获得\(w_i\)的权值，第二次经过该边获得\(w_i-1\)的权值，第三次为\(w_i-1-2\)，第四次\(w_i-1-2-3\)，直到该边权值减到<=0之后，经过该边不再获得任何权值。从起点s出发，求一条能获得最大权值和的路径，输出获得的最大权值和。其中\(w_i<=10^8,1<=n<=10^6,0<=m<=10^6\)。

    题解：考虑到在一个强联通分量内的点间的路径肯定是全部用完是最优的，所以可以先强联通分量缩点，然后图就变成了一棵树，树上路径一定最多经过一次。剩下要求的就是一个强联通分量中所有路径用完的权值，即每条路径用完的权值和。这个写出式子求个和就好了，比较简单就不写了。

    PS：由于数据量是\(10^6\)级别的，所以如果重构图要去重边的话不能带log，否则会TLE。（来自Div2 FST选手的怨念）（当然不用删重边够做了）

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;

int head[maxn],nxt[maxn],E[maxn],D[maxn],Ecnt;
int head2[maxn],nxt2[maxn],E2[maxn],Ecnt2;
long long D2[maxn];
int DFN[maxn],Low[maxn],Index;
bool Instack[maxn];
int Stack[maxn],top;
int ID[maxn],cnt;
int vis[maxn];
long long f[maxn];
long long Val[maxn];
long long ans;
int n,m,s;

long long Get_Val(int x)
{
	long long res=0;
	long long l=0,r=100000,mid;
	while (l<r)
	{
		mid=(l+r+1)>>1;
		if (mid*(mid+1)/2<=x) l=mid;else r=mid-1;
	}
	res=(l+1)*x-(l*l*l+3*l*l+2*l)/6;
	return res;
}

void Add_Edge(int x,int y,int w) {nxt[++Ecnt]=head[x];head[x]=Ecnt;E[Ecnt]=y;D[Ecnt]=w;}
void Add_Edge2(int x,int y,long long w) {nxt2[++Ecnt2]=head2[x];head2[x]=Ecnt2;E2[Ecnt2]=y;D2[Ecnt2]=w;}

void Tarjan(int x)
{
    DFN[x]=Low[x]=++Index;
    Instack[x]=true;
    Stack[++top]=x;
    for (int i=head[x];i;i=nxt[i])
        if (!DFN[E[i]]) Tarjan(E[i]),Low[x]=min(Low[x],Low[E[i]]);
        else if (Instack[E[i]]) Low[x]=min(Low[x],DFN[E[i]]);
    if (DFN[x]==Low[x])
    {
        cnt++;
        while (Instack[x])
        {
            int u=Stack[top--];
            Instack[u]=false;
            ID[u]=cnt;
        }
    }
}

long long DFS(int x)
{
	for (int i=head2[x];i;i=nxt2[i])
	{
		if (vis[E2[i]]) f[x]=max(f[x],f[E2[i]]+D2[i]);
		else vis[E2[i]]=1,f[x]=max(f[x],DFS(E2[i])+D2[i]);
	}
	f[x]+=Val[x];
	return f[x];
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
	{
		int x,y,w;
		scanf("%d%d%d",&x,&y,&w);
		Add_Edge(x,y,w);
	}
	scanf("%d",&s);
	Tarjan(s);
	for (int i=1;i<=n;i++)
	{
		for (int j=head[i];j;j=nxt[j])
			if (ID[E[j]]==ID[i]) Val[ID[i]]+=Get_Val(D[j]);
			else Add_Edge2(ID[i],ID[E[j]],D[j]);
	}
	printf("%I64d\n",DFS(ID[s]));
	return 0;
}