求助
查看原帖
求助
315005
White_gugu楼主2021/7/6 16:22
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{
	long long s,t,sp;
}kk[400400];
int n,m,q;
long long num[200200];
long long val[200200];
long long fa[200200];
long long lc[200200];
long long head[400200];
long long to[400200];
long long next[400400];
long long ouo[400400];
long long f[200100][22];
long long g[200100][22];
long long dep[200200];
long long root=1;
long long cnt=0;
long long mid(long long a,long long b)
{
	if(a<b)
	return a;
	else
	return b;
}
void build(int u,int v,long long w)
{
	to[cnt]=v;
	ouo[cnt]=w;
	next[cnt]=head[u];
	head[u]=cnt;
	cnt++;
}
bool cmp(node x,node y)
{
	return x.sp>y.sp;
}
int getf(int x)
{
	if(fa[x]==x) return x;
	fa[x]=getf(fa[x]); return fa[x];
}
void hb(int x,int y)
{
	fa[getf(x)]=getf(y);
	fa[x]=getf(x);
	fa[y]=getf(y);
}
void find(int x,int father)
{
	dep[x]=dep[father]+1;
	for(int i=1;(1<<i)<=dep[x];i++)
	{
		f[x][i]=f[f[x][i-1]][i-1];
		g[x][i]=min(g[x][i-1],g[f[x][i-1]][i-1]);
	} 
	for(int i=head[x];i!=-1;i=next[i])
	{
		int y=to[i];
		if(y==father)
		continue;
		g[y][0]=ouo[i];
		f[y][0]=x;
		find(y,x);
	}
	return;
}
long long lca(int u,int v)
{
	long long maxn=21000000000;
	if(dep[u]<=dep[v])
	swap(u,v);
	for(int i=20;i>=0;i--)
    {
		if(dep[f[u][i]]>=dep[v])
		{
		   maxn=min(maxn,g[u][i]);
			u=f[u][i];
		}
		if(u==v)
		return maxn;
	}	   
	for(int i=20;i>=0;i--)
	{
		if(f[u][i]!=f[v][i])
		{
		    maxn=min(maxn,min(g[u][i],g[v][i]));
			u=f[u][i],v=f[v][i];
		}
	}
	maxn=min(maxn,min(g[u][0],g[v][0]));
	return maxn;
}
int main()
{
	memset(head,-1,sizeof(head));
	memset(g,127,sizeof(g));
	scanf("%d %d %d",&n,&m,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&num[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
	for(int i=1;i<=m;i++)
	scanf("%lld %lld %lld",&kk[i].s,&kk[i].t,&kk[i].sp);
	for(int i=1;i<=q;i++)
	{
		scanf("%lld",&lc[i]);
		if(i==1)
		continue;
		m++;
		kk[m].s=lc[i-1];
		kk[m].t=lc[i];
		kk[m].sp=21000000000;
	}
	sort(kk+1,kk+m+1,cmp);
	for(int i=1;i<=n;i++)
	fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int p1=kk[i].s;
		int p2=kk[i].t;
		if(getf(p1)==getf(p2))
		continue;
		build(p1,p2,kk[i].sp);
		hb(p1,p2);
	}	
	find(root,0);
	long long ca=val[num[1]];
	if(ca<0)
	{
		ca=0;
		printf("0\n");
    }
	for(int i=2;i<=n;i++)
	{
		long long now=num[i];
		long long man=lca(num[i-1],now);
		ca=min(ca,man);
		if(val[now]<0)
		{
			if(ca+val[now]<0)
			{
				printf("%lld\n",ca);
				ca=0;
			}
			else
			{
				printf("%lld\n",-val[now]);
				ca+=val[now];
			}
		}
		else
			ca+=val[now];
	}
}

一直爆0,但是本蒟蒻看不出错误 希望各位大佬帮帮忙QAQ

2021/7/6 16:22
加载中...