#2861 城市交易 【最大瓶頸路+貪心】

**【描述】**
L在N個不同的城市做生意，他收到了N個不同城市的N份交易訂單。在這N個城市之間有一些低速公路，這些低速公路都有自己的一個載重上限，這限制了你在這條公路上前進的時候能夠攜帶的貨物數量。除了低速公路之外，還有些城市修了慢速鐵路站。對於修了慢速鐵路站的城市，你可以乘坐慢速火車在這些城市之間往返而不受載重上限的限制。

L現在要按照順序來處理這N份訂單，他可以自由選擇自己的路線。這N份訂單每份訂單可能是要從客戶中買進一些貨物，或者售出一些貨物，並且有可以交易的上限存在。L希望自己在交易完最後一筆訂單之後自己不會剩下貨物，並且在整個過程中不會出現因載重限制丟棄貨物的情況（意味著你並不會每次都以最大量買入）。在滿足以上所有條件的情況下，L希望自己的交易量最大（即買入賣出都儘量多），那麼最大的交易量應該是怎樣的呢？

**【數據範圍與規定】**

對於20%的數據，N≤100，M≤200。

對於50%的數據，N≤3000，M≤6000。

對於100%的數據，N≤10^5，N-1≤M≤2*10^5，0≤Q≤N，0<|x|<10^9，保證任意兩個城市之間可以通過低速公路連通。

做法:

註意建圖的細節。

先跑最大瓶頸路（最大生成樹+lca維護兩點間最小距離）， 最後處理成一條鏈貪心轉移即可（只需要輸出賣出的方案）

代碼：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define re register
  4 #define int long long
  5 const int INF=1e14+9;
  6 const int maxm=6e5+10,maxn=2e5+10;
  7 int n,m,Q,on;
  8 struct edge{
  9 int v,nxt,w;
 10 }e[maxm];
 11 int head[maxn],cnt=0;
 12 inline void _add(int u,int v,int w){
 13 e[++cnt]=(edge){v,head[u],w};
 14 head[u]=cnt;
 15 }
 16 struct pi{
 17 int u,v,w;
 18 }p[maxm];
 19 bool cmp(pi a,pi b){
 20 return a.w>b.w;
 21 }
 22 int a1,a2,a3;
 23 int ord[maxn];
 24 bool col[maxn];
 25 int ff[maxn];
 26 int find(int u){
 27 return ff[u]==0? u:ff[u]=find(ff[u]);
 28 }
 29 inline void build(){
 30 sort(p+1,p+on+1,cmp);
 31 for(int i=1;i<=on;++i){
 32 a1=p[i].u,a2=p[i].v,a3=p[i].w;
 33 int f1=find(a1),f2=find(a2);
 34 if(f1==f2)continue;
 35 ff[f1]=f2;
 36 _add(a1,a2,a3);_add(a2,a1,a3);
 37 //if(amt==n-Q+1)break;
 38 }
 39 }
 40 int fa[maxn][50],mn[maxn][50],dep[maxn];
 41 //mn contain this now
 42 //fa start from the last one
 43 void Run(int u){
 44 for(int i=1;(1<<i)<=dep[u];++i){
 45 fa[u][i]=fa[fa[u][i-1]][i-1];
 46 mn[u][i]=min(mn[u][i-1],mn[fa[u][i-1]][i-1]);
 47 }
 48 for(int i=head[u];i;i=e[i].nxt){
 49 int v=e[i].v;
 50 if(!dep[v]){
 51 dep[v]=dep[u]+1;
 52 fa[v][0]=u;mn[v][0]=e[i].w;
 53 Run(v);
 54 }
 55 }
 56 
 57 }
 58 inline int get(int a,int b){
 59 if(dep[a]<dep[b])swap(a,b);
 60 int gap=dep[a]-dep[b];
 61 int ret=INF;
 62 for(int i=0;(1<<i)<=gap;++i){
 63 if(gap&(1<<i)){
 64 ret=min(ret,mn[a][i]);
 65 a=fa[a][i];    
 66 }
 67 }
 68 if(a==b)return ret;
 69 for(int i=18;i>=0;--i){
 70 if(fa[a][i]!=fa[b][i]){
 71 ret=min(ret,min(mn[a][i],mn[b][i]));
 72 a=fa[a][i],b=fa[b][i];
 73 }
 74 }
 75 return min(ret,min(mn[a][0],mn[b][0]));    
 76 }
 77 int limit[maxn];
 78 int f[maxn];
 79 int ans[maxn],top=0;
 80 signed main(){
 81 scanf("%lld%lld%lld",&n,&m,&Q);
 82 for(int re i=1;i<=n;++i)scanf("%lld",&ord[i]);
 83 for(int re i=1;i<=n;++i)scanf("%lld",&limit[i]);
 84 for(int re i=1;i<=m;++i){
 85 scanf("%lld%lld%lld",&a1,&a2,&a3);
 86 p[i]=(pi){a1,a2,a3};
 87 }
 88 
 89 for(int re i=1;i<=Q;++i){
 90 scanf("%lld",&a1);
 91 col[a1]=1;
 92 }
 93 //    for(int re i=1;i<=n;++i){
 94 //    p[i].u=col[p[i].u],p[i].v=col[p[i].v];
 95 //    }
 96 on=m;
 97 if(Q){
 98 for(int i=1;i<=n;++i){
 99 if(a1==i||col[i]==0)continue;
100 p[++on]=(pi){a1,i,INF};
101 }
102 }
103 build();
104 dep[1]=1;
105 //for(int i=0;i<=19;++i)mn[1][i]=1000000009;
106 Run(1);
107 //    cerr<<mn[2][0]<<endl;
108 //    for(int u=1;u<=n;++u){
109 //    for(int i=head[u];i;i=e[i].nxt){
110 //    int v=e[i].v;
111 //    cerr<<u<<" "<<v<<" "<<e[i].w<<endl;
112 //    }
113 //    }
114 f[1]=max(0ll,limit[ord[1]]);
115 if(limit[ord[1]]<0)ans[++top]=0;
116 for(int re i=2;i<=n;++i){
117 int u=ord[i],l=get(u,ord[i-1]);
118 //    cerr<<f[u]<<endl;
119 //    cerr<<" u= "<<u<<" l= "<<l<<" limit= "<<limit[u]<<endl;
120 int k=min(f[i-1],l);
121 f[i]=max(0ll,k+limit[u]);
122 if(limit[u]<0)ans[++top]=min(k,-limit[u]);
123 }
124 //    for(int i=1;i<=n;++i)cerr<<limit[i]<<endl;
125 for(int re i=1;i<=top;++i)printf("%lld\n",ans[i]);
126 return 0;
127 }