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 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
| #include<bits/stdc++.h> #define maxn 80005 using namespace std; struct eee{ int to; int next; int w; float p; }edge[maxn*3],e[maxn*3]; int root[maxn],root2[maxn],dfn[maxn],low[maxn],visited[maxn],s[maxn],degree[maxn],num[maxn],amount[maxn],ans[maxn],flag[maxn],cnt,cnt2,tot,top,deep,n,m; stack<int>ss; void add(int x,int y,int w,float p){ edge[++cnt].to=y; edge[cnt].w=w; edge[cnt].next=root[x]; edge[cnt].p=p; root[x]=cnt; } void add2(int x,int y,int w,float p){ degree[y]++; e[++cnt2].next=root2[x]; e[cnt2].to=y; e[cnt2].w=w; e[cnt2].p=p; root2[x]=cnt2; } void tarjan(int u){ visited[u]=1; dfn[u]=low[u]=++deep; s[++top]=u; for(int i=root[u];i;i=edge[i].next){ int v=edge[i].to; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(visited[v]){ low[u]=min(low[u],low[v]); } } if(dfn[u]==low[u]){ visited[u]=0; num[u]=++tot; while(s[top]!=u){ visited[s[top]]=0; num[s[top--]]=tot; } top--; } } int main(){ cin>>n>>m; for(int i=1;i<=m;i++){ int x, y, w; float p; cin>>x>>y>>w>>p; add(x,y,w,p); } int start; scanf("%d",&start); for(int i=1;i<=n;i++){ if(!dfn[i])tarjan(i); } for(int i=1;i<=n;i++){ for(int j=root[i];j;j=edge[j].next){ int v=edge[j].to,w=edge[j].w; float p=edge[j].p; if(num[i]==num[v]){ while(w!=0){ amount[num[i]]+=w; w=(int)((p)*w); } } else{ add2(num[i],num[v],w,p); } } } for(int i=1;i<=tot;i++){ if(!degree[i])ss.push(i); } ans[num[start]]=amount[num[start]]; flag[num[start]]=1; int res=ans[num[start]]; while(!ss.empty()){ int x=ss.top(); ss.pop(); for(int i=root2[x];i;i=e[i].next){ int v=e[i].to,w=e[i].w; degree[v]--; if(!degree[v])ss.push(v); if(flag[x]){ ans[v]=max(ans[v],ans[x]+w+amount[v]); res=max(res,ans[v]); flag[v]=1; } } } if(tot==1){ printf("%d",ans[1]); } else printf("%d",res); return 0; }
|