货车运输升级版
从u到v，能卖出的黄金取决于路径上的最大值的最小值->Kruskal重构树
还有个贪心的思想，遇到黄金能买就买，因为就算我们买多了，我们可以假装上次没有买这么多。
那怎么处理铁路车站呢？只需建值为INF的边即可
然后就模拟了
（话说谁能给我讲一下Kruskal重构树各个数组到底开多大啊 全凭感觉开）
#include<bits/stdc++.h> #define ll long long const int N=1e5+5; const ll INF=1000000000000000ll; using namespace std; int n,m,q,sx[N],father[2*N]; ll p[N]; struct Edge { int from,to,next; ll val; }e[4*N],edge[8*N]; inline bool cmp(const Edge &a,const Edge &b) { return a.val>b.val; } inline int getfather(int x) { if(father[x]==x) return x; return father[x]=getfather(father[x]); } int tot,first[2*N]; ll v[2*N]; inline void addedge(int x,int y) { tot++; edge[tot].to=y; edge[tot].next=first[x]; first[x]=tot; } void Kruskal_Rebuild() { for(int i=1;i<=2*n;i++) father[i]=i; sort(e+1,e+m+1,cmp); int cnt=0,sign=n; for(int i=1;i<=m;i++) { int fx=getfather(e[i].from); int fy=getfather(e[i].to); if(fx==fy) continue; cnt++; sign++; father[fx]=father[fy]=sign; v[sign]=e[i].val; addedge(fx,sign); addedge(sign,fx); addedge(fy,sign); addedge(sign,fy); if(cnt==n-1) break; } } int depth[2*N],up[2*N][21]; void dfs(int now,int fa) { up[now][0]=fa; depth[now]=depth[fa]+1; for(int i=1;i<=19;i++) up[now][i]=up[up[now][i-1]][i-1]; for(int u=first[now];u;u=edge[u].next) { int vis=edge[u].to; if(vis==fa) continue; dfs(vis,now); } } inline int LCA(int x,int y) { if(depth[x]<depth[y]) swap(x,y); for(int i=19;i>=0;i--) if(depth[up[x][i]]>=depth[y]) x=up[x][i]; if(x==y) return x; for(int i=19;i>=0;i--) if(up[x][i]!=up[y][i]) x=up[x][i],y=up[y][i]; return up[x][0]; } void Overspeeding() { int last=sx[1]; ll w=p[sx[1]]; if(w<0) cout<<"0"<<endl,w=0; for(int i=2;i<=n;i++) { ll limit=v[LCA(last,sx[i])]; w=min(limit,w); if(p[sx[i]]>0) //购入 w+=p[sx[i]]; else { if(w>abs(p[sx[i]])) w+=p[sx[i]],cout<<-p[sx[i]]<<endl; else cout<<w<<endl,w=0; } last=sx[i]; } } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin>>n>>m>>q; for(int i=1;i<=n;i++) cin>>sx[i]; for(int i=1;i<=n;i++) cin>>p[i]; for(int i=1;i<=m;i++) cin>>e[i].from>>e[i].to>>e[i].val; int x; if(q) cin>>x; for(int i=2,y;i<=q;i++) { cin>>y; e[++m].from=x; e[m].to=y; e[m].val=INF; } Kruskal_Rebuild(); dfs(2*n-1,0); Overspeeding(); return 0; }原文链接：https://blog.csdn.net/Patrickpwq/article/details/86634676?ops_request_misc=&request_id=141897c015e84556a2c5c4f6211972e6&biz_id=&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~koosearch~default-1-86634676-null-null.268%5Ev1%5Econtrol&utm_term=%E8%A5%BF%E5%AE%89%E6%91%A9%E6%89%98%E8%BD%A6
