题解 P3280 【[SCOI2013]摩托车交易 】
Azazеl
·
·
题解
P3280 [SCOI2013]摩托车交易
题意
题解
$~~~~$ 先来看两个限制怎么解决，由于买入的时候不需要输出，其实我们完全可以全部买下来，然后在路上丢掉。（其实丢掉多少就是少买多少）所以直接忽略限制（b） 即可。然后你会发现限制（a）也可以用这样的方法忽略掉，所以我们每次买入直接全买就可以了。~~所以这两个限制完全就是来干扰的。~~
$~~~~$ 再来看剩下的部分，两种道路，有限制时我们可以想到 [P1967 货车运输](https://www.luogu.com.cn/problem/P1967 "路径上权值最小值最大") ，用 Kruskal重构树 将权值从大到小排序即可。至于没有限制时，我们完全可以转化为其限制为无限大（本题的 $INF$ 开到 $10^9$ 即可），那就又变成第一种了。
$~~~~$ 所以这道题就解决了。注意数组要开够大，有时候它不够会爆 `WA` 而不是 `RE`.
---
#### 代码
```cpp
#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
const ll INF=1e18;
ll n,m,p;
ll tot,fa[400005],order[400005],gold[400005];
vector <ll> G[400005];
struct Edge{
ll u,v;
ll w;
Edge(){}
Edge(ll U,ll V,ll W){u=U,v=V,w=W;}
}E[600005];
ll findSet(ll x)
{
if(fa[x]==x) return x;
else return fa[x]=findSet(fa[x]);
}
void Kru()
{
ll cnt=0;
for(ll i=1;i<=m+max(p,1ll)-1;i++)
{
ll u=E[i].u,v=E[i].v,w=E[i].w;
u=findSet(u),v=findSet(v);
if(u!=v)
{
tot++;cnt++;
gold[tot]=w;
G[u].push_back(tot); G[tot].push_back(u); fa[u]=tot;
G[v].push_back(tot); G[tot].push_back(v); fa[v]=tot;
}
if(cnt==n-1) return;
}
}
inline bool cmp(Edge x,Edge y){return x.w>y.w;}
ll dep[400005],f[400005][20],lg[400005];
void dfs(ll u,ll fat)
{
dep[u]=dep[fat]+1;
f[u][0]=fat;
for(ll i=1;i<=lg[dep[u]];i++) f[u][i]=f[f[u][i-1]][i-1];
for(ll i=0;i<G[u].size();i++)
{
ll v=G[u][i];
if(v==fat) continue;
dfs(v,u);
}
}
ll query(ll x,ll y)
{
if(dep[x]<dep[y]) swap(x,y);
while(dep[x]>dep[y]) x=f[x][lg[dep[x]-dep[y]]-1];
if(x==y) return gold[x];
for(ll k=lg[dep[x]]-1;k>=0;k--)
{
if(f[x][k]!=f[y][k]) x=f[x][k],y=f[y][k];
}
return gold[f[x][0]];
}
int main() {
ll root;
scanf("%lld %lld %lld",&n,&m,&p);
for(ll i=1;i<=n;i++) fa[i]=i,lg[i]=lg[i-1]+(1<<lg[i-1]==i),scanf("%lld",&order[i]);
for(ll i=1;i<=n;i++) fa[i+n]=i+n,lg[i+n]=lg[i+n-1]+(1<<lg[i+n-1]==i+n),scanf("%lld",&gold[i]);
for(ll i=1,u,v,w;i<=m;i++)
{
scanf("%lld %lld %lld",&u,&v,&w);
E[i]=Edge(u,v,w);
}
if(p) scanf("%lld",&root);
for(ll i=1,q;i<p;i++)
{
scanf("%lld",&q);
E[m+i]=Edge(root,q,INF);
}
tot=n;
sort(E+1,E+m+max(p,1ll),cmp);
Kru();
dfs(tot,0);
ll now=gold[order[1]];
if(now<=0) puts("0"),now=0;
for(ll i=1;i<n;i++)
{
ll x=order[i],y=order[i+1];
ll re=query(x,y);
now=min(now,re);
if(gold[y]>0) now+=gold[y];
else
{
if(now+gold[y]>=0) printf("%lld\n",-gold[y]),now+=gold[y];
else printf("%lld\n",now),now=0;
}
}
return 0;
}
```