NC20569. [SCOI2013]摩托车交易
描述
输入描述
输入的第一行有三个整数n, m, q，分别表示城市数，连通城市的高速公路数和有列车站的城市数。接下来的一行有n 个数，每个数均不相同，且值介于1 到n 之间，代表订单的顺序。第三行有n 个数，第i 个数表示i 号城市的订单的上限额bi，bi 为正值表示该订单为买入交易（针对mzry1992 而言），上限为bi，bi 为负值表示该订单为卖出交易（同样针对mzry1992 而言）上限为 -bi。接下来的m 行每行有三个数，u, v, w，表示城市u 和城市v 之间有一条载重上限为w 的高速公路，这里假定所有高速公路都是双向的，城市的序号是从1 到n 的。输入的最后一行有q个数，代表有列车站城市的序号。对于20% 数据，n ≤ 100，m ≤ 200对于50% 数据，n ≤ 3000，m ≤ 6000对于100% 数据，1 ≤ n ≤ 10^5，n - 1 ≤ m ≤ 2*[1]10^5，0 ≤ q ≤ n，0 < |bi| < 10^9，0 < w < 10^9，保证任意两个城市之间是通过高速公路连通的。
输出描述
按照订单顺序对于每个卖出交易，输出一行，该行只有一个整数x，表示卖出黄金的量。
示例1
输入:
3 3 2 2 3 1 -6 5 -3 1 3 5 2 3 2 2 1 6 1 3
输出:
3 2
说明:
第一组样例：其中一种合法的方案是最初从2 号城市买入5 单位的黄金，先走第三条高速公路到1 号城市，然后再坐列车到3 号城市，在3 号城市卖出3 单位的黄金，然后乘坐列车到1 城市，在1 号城市卖出2 单位的黄金。示例2
输入:
4 4 0 1 2 3 4 5 4 -6 -1 1 2 4 2 3 100 3 4 1 4 1 4
输出:
6 1
说明:
第二组样例：其中一种合法的方案是最初从1 号城市买入4 单位的黄金，走第一条高速公路，在2 号城市买入3 单位的黄金，走第二条高速公路，在三城市点卖出6 单位的黄金，走第三条高速公路，在4 号城市卖出1 单位的黄金。C++(g++ 7.5.0) 解法, 执行用时: 150ms, 内存消耗: 41792K, 提交时间: 2023-03-23 15:03:21
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int getint()
{
int i=0,f=1;char c;
for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
if(c=='-')f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
const int N=100005;
const ll INF=1e18;
int n,m,q,a[N],p[N];
int tot,first[N],nxt[N<<1],to[N<<1];
ll w[N<<1],mi[N][20];
int dep[N],id[N],fa[N][20];
struct edge{int x,y;ll w;}bian[N<<1];
inline bool cmp(const edge &a,const edge &b){return a.w>b.w;}
inline int find(int x){return id[x]==x?x:id[x]=find(id[x]);}
inline void add(int x,int y,ll z)
{
nxt[++tot]=first[x],first[x]=tot,to[tot]=y,w[tot]=z;
nxt[++tot]=first[y],first[y]=tot,to[tot]=x,w[tot]=z;
}
void kruskal()
{
sort(bian+1,bian+m+1,cmp);
for(int i=1;i<=m;i++)
{
int x=find(bian[i].x),y=find(bian[i].y);
if(x!=y)id[y]=x,add(bian[i].x,bian[i].y,bian[i].w);
}
}
void dfs(int u)
{
for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=1;i<20;i++)mi[u][i]=min(mi[u][i-1],mi[fa[u][i-1]][i-1]);
for(int e=first[u];e;e=nxt[e])
{
int v=to[e];
if(v==fa[u][0])continue;
fa[v][0]=u,dep[v]=dep[u]+1,mi[v][0]=w[e];
dfs(v);
}
}
ll find_min(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
ll res=INF;int det=dep[x]-dep[y];
for(int i=0;i<20;i++)if(det&(1<<i))res=min(res,mi[x][i]),x=fa[x][i];
for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])
res=min(res,min(mi[x][i],mi[y][i])),x=fa[x][i],y=fa[y][i];
if(x==y)return res;
else return min(res,min(mi[x][0],mi[y][0]));
}
signed main()
{
//freopen("lx.in","r",stdin);
//freopen("lx.out","w",stdout);
n=getint(),m=getint(),q=getint();
for(int i=1;i<=n;i++)p[i]=getint();
for(int i=1;i<=n;i++)a[i]=getint(),id[i]=i;
for(int i=1;i<=m;i++)bian[i].x=getint(),bian[i].y=getint(),bian[i].w=getint();
int x,y;if(q)x=getint();
for(int i=2;i<=q;i++)y=getint(),id[y]=x,add(x,y,INF);
kruskal();dfs(1);
ll cur=0;a[p[1]]>0?cur=a[p[1]]:puts("0");
for(int i=1;i<n;i++)
{
int x=p[i],y=p[i+1];ll t=find_min(x,y);
cur=min(cur,t);
if(a[y]>0)cur+=a[y];
else printf("%lld\n",min(cur,(ll)-a[y])),cur=max(0ll,cur+a[y]);
}
return 0;
}
C++ 解法, 执行用时: 126ms, 内存消耗: 35464K, 提交时间: 2022-05-22 16:14:36
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int getint()
{
int i=0,f=1;char c;
for(c=getchar();(c!='-')&&(c<'0'||c>'9');c=getchar());
if(c=='-')f=-1,c=getchar();
for(;c>='0'&&c<='9';c=getchar())i=(i<<3)+(i<<1)+c-'0';
return i*f;
}
const int N=100005;
const ll INF=1e18;
int n,m,q,a[N],p[N];
int tot,first[N],nxt[N<<1],to[N<<1];
ll w[N<<1],mi[N][20];
int dep[N],id[N],fa[N][20];
struct edge{int x,y;ll w;}bian[N<<1];
inline bool cmp(const edge &a,const edge &b){return a.w>b.w;}
inline int find(int x){return id[x]==x?x:id[x]=find(id[x]);}
inline void add(int x,int y,ll z)
{
nxt[++tot]=first[x],first[x]=tot,to[tot]=y,w[tot]=z;
nxt[++tot]=first[y],first[y]=tot,to[tot]=x,w[tot]=z;
}
void kruskal()
{
sort(bian+1,bian+m+1,cmp);
for(int i=1;i<=m;i++)
{
int x=find(bian[i].x),y=find(bian[i].y);
if(x!=y)id[y]=x,add(bian[i].x,bian[i].y,bian[i].w);
}
}
void dfs(int u)
{
for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=1;i<20;i++)mi[u][i]=min(mi[u][i-1],mi[fa[u][i-1]][i-1]);
for(int e=first[u];e;e=nxt[e])
{
int v=to[e];
if(v==fa[u][0])continue;
fa[v][0]=u,dep[v]=dep[u]+1,mi[v][0]=w[e];
dfs(v);
}
}
ll find_min(int x,int y)
{
if(dep[x]<dep[y])swap(x,y);
ll res=INF;int det=dep[x]-dep[y];
for(int i=0;i<20;i++)if(det&(1<<i))res=min(res,mi[x][i]),x=fa[x][i];
for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])
res=min(res,min(mi[x][i],mi[y][i])),x=fa[x][i],y=fa[y][i];
if(x==y)return res;
else return min(res,min(mi[x][0],mi[y][0]));
}
signed main()
{
//freopen("lx.in","r",stdin);
//freopen("lx.out","w",stdout);
n=getint(),m=getint(),q=getint();
for(int i=1;i<=n;i++)p[i]=getint();
for(int i=1;i<=n;i++)a[i]=getint(),id[i]=i;
for(int i=1;i<=m;i++)bian[i].x=getint(),bian[i].y=getint(),bian[i].w=getint();
int x,y;if(q)x=getint();
for(int i=2;i<=q;i++)y=getint(),id[y]=x,add(x,y,INF);
kruskal();dfs(1);
ll cur=0;a[p[1]]>0?cur=a[p[1]]:puts("0");
for(int i=1;i<n;i++)
{
int x=p[i],y=p[i+1];ll t=find_min(x,y);
cur=min(cur,t);
if(a[y]>0)cur+=a[y];
else printf("%lld\n",min(cur,(ll)-a[y])),cur=max(0ll,cur+a[y]);
}
return 0;
}