自动搬运

查看原文

来自洛谷，原作者为

	Azazеl Just the smallest grain in the sands

搬运于2025-08-24 21:47:17，当前版本为作者最后更新于2020-09-01 22:18:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P3280 [SCOI2013]摩托车交易

题意

$~~~~$ 给出需要拜访的城市的顺序，每个城市可以买入或卖出给定最大值以内的数量的金条。有两种道路，一种上面限制携带的金条个数，另一种不限制。在每个城市的买入或卖出的金条尽量最大，求每次卖出的金条个数值。

题解

$~~~~$ 其实我写的题意已经把这题简化了。

$~~~~$ 先来看两个限制怎么解决，由于买入的时候不需要输出，其实我们完全可以全部买下来，然后在路上丢掉。（其实丢掉多少就是少买多少）所以直接忽略限制（b） 即可。然后你会发现限制（a）也可以用这样的方法忽略掉，所以我们每次买入直接全买就可以了。所以这两个限制完全就是来干扰的。

$~~~~$ 再来看剩下的部分，两种道路，有限制时我们可以想到 P1967 货车运输 ，用 Kruskal重构树 将权值从大到小排序即可。至于没有限制时，我们完全可以转化为其限制为无限大（本题的 $INF$ 开到 $10^9$ 即可），那就又变成第一种了。

$~~~~$ 所以这道题就解决了。注意数组要开够大，有时候它不够会爆 WA 而不是 RE.

代码

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