#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 }