社区讨论

我是蒟蒻,蜜汁TLE#3,大佬求助

P3627[APIO2009] 抢掠计划参与者 6已保存回复 8

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
8 条
当前快照
1 份
快照标识符
@mi6vtj9w
此快照首次捕获于
2025/11/20 11:38
4 个月前
此快照最后确认于
2025/11/20 11:38
4 个月前
查看原帖
快读,register,printf,++i都用上了
还是凉凉,QAQ
CPP
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
	int next,to,dis;
}edge[500010];
int v_p[500010],n,m,s,p,end[500010],num_edge;
int head[500010],x[500010],y[500010];
inline int read()
{
    int x=0,w=0;char ch=0;
    while(!(ch>='0'&&ch<='9'))
    {
        if(ch=='-') w=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return w?-x:x;
}
inline void add_edge(int from,int to)
{
	edge[++num_edge].next=head[from];
	edge[num_edge].to=to;
	head[from]=num_edge;
}
inline void Add_edge(int from,int to,int dis)
{
	edge[++num_edge].next=head[from];
	edge[num_edge].to=to;
	edge[num_edge].dis=dis;
	head[from]=num_edge;
}
int low[500010],dfn[500010],st[500010],in[500010],times,top,cnt;
int color[500010],size[500010];
void tarjan(int x)
{
	int child;
	times++;
	low[x]=dfn[x]=times;
	st[++top]=x;
	in[x]=1;
	for(register int i=head[x];i;i=edge[i].next)
	{
		child=edge[i].to;
		if(!dfn[child])
		{
			tarjan(child);
			low[x]=min(low[x],low[child]);
		}
		else if(in[child]) low[x]=min(low[x],dfn[child]);
	}
	if(low[x]==dfn[x])
	{
		int num;
		cnt++;
		do
		{
			num=st[top--];
			in[num]=0;
			color[num]=cnt;
			size[cnt]+=v_p[num];
		}
		while(num!=x);
	}
}
priority_queue<pair<int,int> > q;
int d[500010],v[500010];
inline void SPFA()
{
	d[color[s]]=size[color[s]];
	q.push(make_pair(size[color[s]],color[s]));
	while(q.size())
	{
		int x=q.top().second;
		q.pop();
		v[x]=0;
		for(register int i=head[x];i;i=edge[i].next)
		{
			int y=edge[i].to,z=edge[i].dis;
			if(d[y]<d[x]+z)
			{
				d[y]=d[x]+z;
				if(!v[y]) { q.push(make_pair(d[y],y)); v[y]=1;}
			}
		}
	}
}
int main(){
	n=read();
	m=read();
	for(register int i=1;i<=m;++i)
	{
		x[i]=read(); y[i]=read();
		add_edge(x[i],y[i]);
	}
	for(register int i=1;i<=n;++i)
	  v_p[i]=read();
	s=read();
	p=read();
	for(register int i=1;i<=p;++i)
	  end[i]=read();
	for(register int i=1;i<=n;++i)
	  if(!dfn[i]) tarjan(i);
	memset(edge,0,sizeof(edge));
    memset(head,0,sizeof(head));
    num_edge=0;
    for(register int i=1;i<=m;++i) 
	  if(color[x[i]]!=color[y[i]]) Add_edge(color[x[i]],color[y[i]],size[color[y[i]]]);
	SPFA();
	int maxn=0;
	for(register int i=1;i<=p;++i)
	  maxn=max(maxn,d[color[end[i]]]);
	printf("%d",maxn);
}

回复

8 条回复,欢迎继续交流。

正在加载回复...