[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; }