**[描述] **
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 维护两点间最小距离), 最后处理成一条链贪心转移即可 (只需要输出卖出的方案)
代码:
- #include<bits/stdc++.h>
- using namespace std;
- #define re register
- #define int long long
- const int INF=1e14+9;
- const int maxm=6e5+10,maxn=2e5+10;
- int n,m,Q,on;
- struct edge{
- int v,nxt,w;
- }e[maxm];
- int head[maxn],cnt=0;
- inline void _add(int u,int v,int w){
- e[++cnt]=(edge){v,head[u],w};
- head[u]=cnt;
- }
- struct pi{
- int u,v,w;
- }p[maxm];
- bool cmp(pi a,pi b){
- return a.w>b.w;
- }
- int a1,a2,a3;
- int ord[maxn];
- bool col[maxn];
- int ff[maxn];
- int find(int u){
- return ff[u]==0? u:ff[u]=find(ff[u]);
- }
- inline void build(){
- sort(p+1,p+on+1,cmp);
- for(int i=1;i<=on;++i){
- a1=p[i].u,a2=p[i].v,a3=p[i].w;
- int f1=find(a1),f2=find(a2);
- if(f1==f2)continue;
- ff[f1]=f2;
- _add(a1,a2,a3);_add(a2,a1,a3);
- //if(amt==n-Q+1)break;
- }
- }
- int fa[maxn][50],mn[maxn][50],dep[maxn];
- //mn contain this now
- //fa start from the last one
- void Run(int u){
- for(int i=1;(1<<i)<=dep[u];++i){
- fa[u][i]=fa[fa[u][i-1]][i-1];
- mn[u][i]=min(mn[u][i-1],mn[fa[u][i-1]][i-1]);
- }
- for(int i=head[u];i;i=e[i].nxt){
- int v=e[i].v;
- if(!dep[v]){
- dep[v]=dep[u]+1;
- fa[v][0]=u;mn[v][0]=e[i].w;
- Run(v);
- }
- }
- }
- inline int get(int a,int b){
- if(dep[a]<dep[b])swap(a,b);
- int gap=dep[a]-dep[b];
- int ret=INF;
- for(int i=0;(1<<i)<=gap;++i){
- if(gap&(1<<i)){
- ret=min(ret,mn[a][i]);
- a=fa[a][i];
- }
- }
- if(a==b)return ret;
- for(int i=18;i>=0;--i){
- if(fa[a][i]!=fa[b][i]){
- ret=min(ret,min(mn[a][i],mn[b][i]));
- a=fa[a][i],b=fa[b][i];
- }
- }
- return min(ret,min(mn[a][0],mn[b][0]));
- }
- int limit[maxn];
- int f[maxn];
- int ans[maxn],top=0;
- signed main(){
- scanf("%lld%lld%lld",&n,&m,&Q);
- for(int re i=1;i<=n;++i)scanf("%lld",&ord[i]);
- for(int re i=1;i<=n;++i)scanf("%lld",&limit[i]);
- for(int re i=1;i<=m;++i){
- scanf("%lld%lld%lld",&a1,&a2,&a3);
- p[i]=(pi){a1,a2,a3};
- }
- for(int re i=1;i<=Q;++i){
- scanf("%lld",&a1);
- col[a1]=1;
- }
- // for(int re i=1;i<=n;++i){
- // p[i].u=col[p[i].u],p[i].v=col[p[i].v];
- // }
- on=m;
- if(Q){
- for(int i=1;i<=n;++i){
- if(a1==i||col[i]==0)continue;
- p[++on]=(pi){a1,i,INF};
- }
- }
- build();
- dep[1]=1;
- //for(int i=0;i<=19;++i)mn[1][i]=1000000009;
- Run(1);
- // cerr<<mn[2][0]<<endl;
- // for(int u=1;u<=n;++u){
- // for(int i=head[u];i;i=e[i].nxt){
- // int v=e[i].v;
- // cerr<<u<<""<<v<<" "<<e[i].w<<endl;
- // }
- // }
- f[1]=max(0ll,limit[ord[1]]);
- if(limit[ord[1]]<0)ans[++top]=0;
- for(int re i=2;i<=n;++i){
- int u=ord[i],l=get(u,ord[i-1]);
- // cerr<<f[u]<<endl;
- // cerr<<"u="<<u<<"l="<<l<<"limit="<<limit[u]<<endl;
- int k=min(f[i-1],l);
- f[i]=max(0ll,k+limit[u]);
- if(limit[u]<0)ans[++top]=min(k,-limit[u]);
- }
- // for(int i=1;i<=n;++i)cerr<<limit[i]<<endl;
- for(int re i=1;i<=top;++i)printf("%lld\n",ans[i]);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2957137.html