社区讨论
我是蒟蒻,蜜汁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 条回复,欢迎继续交流。
正在加载回复...