[Codeforces Round #447][Codeforces 894E]Ralph and Mushrooms
题意:给出一个有向图,对于一条边i,其初始权值为wi,第一次经过该边获得wi的权值,第二次经过该边获得wi−1的权值,第三次为wi−1−2,第四次wi−1−2−3,直到该边权值减到<=0之后,经过该边不再获得任何权值。从起点s出发,求一条能获得最大权值和的路径,输出获得的最大权值和。其中wi<=108,1<=n<=106,0<=m<=106。
题解:考虑到在一个强联通分量内的点间的路径肯定是全部用完是最优的,所以可以先强联通分量缩点,然后图就变成了一棵树,树上路径一定最多经过一次。剩下要求的就是一个强联通分量中所有路径用完的权值,即每条路径用完的权值和。这个写出式子求个和就好了,比较简单就不写了。
PS:由于数据量是106级别的,所以如果重构图要去重边的话不能带log,否则会TLE。(来自Div2 FST选手的怨念)(当然不用删重边够做了)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #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; } |