社区讨论
#3 #12 wa,求dalao看看
P3627[APIO2009] 抢掠计划参与者 3已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6x3x2x
- 此快照首次捕获于
- 2025/11/20 12:14 4 个月前
- 此快照最后确认于
- 2025/11/20 12:14 4 个月前
就是个拓扑排序加最长路
CPP#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
struct node{
int from,v,next;
}edge[500001],edge2[500001];
int dfn[500001],low[500001],head[500001],col=0,top=0,num=0,co[500001],si[500001],m,n,w[500001],st,stack[500001],head2[500001];
bool p[500001];int pa[500001],tot[500001],ans,dp[500001],visit[500001],pp[500001];
void add(int from,int to){
edge[++top].v=to;
edge[top].from=from;
edge[top].next=head[from];
head[from]=top;
return;
}
void search(){
queue<int>q;
q.push(st);
visit[st]=1;
dp[co[st]]=tot[co[st]];
while(!q.empty()){
int now=q.front();
q.pop();
for(int i=head[now];i;i=edge[i].next){
int next=edge[i].v;
if(co[now]!=co[next]) {
dp[co[next]]=max(dp[co[next]],tot[co[next]]+dp[co[now]]);
}
if(!visit[next]){
visit[next]=1;
q.push(next);
}
}
}
for(int i=1;i<=top;i++){
ans=max(ans,dp[pa[i]]);
}
}
void tarjan(int now){
dfn[now]=++num;
low[now]=num;
stack[++top]=now;
for(int i=head[now];i;i=edge[i].next){
int next=edge[i].v;
if(!dfn[next]){
tarjan(next);
low[now]=min(low[now],low[next]);
}
else if(!co[next]){
low[now]=min(low[now],low[next]);
}
}
if(low[now]==dfn[now]){
si[++col]++;
co[now]=col;
while(stack[top]!=now){
si[col]++;
co[stack[top]]=col;
top--;
}
top--;
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
top=0;
for(int i=1;i<=n;i++){
cin>>w[i];
}
int pl;
cin>>st>>pl;
for(int i=1;i<=pl;i++){
int dir;
cin>>dir;p[dir]=1;
}
col=0;
for(int i=1;i<=n;i++) {
if(!dfn[i]) tarjan(i);
}
top=0;
for(int i=1;i<=n;i++){
if(p[i]&&!pp[co[i]]){
top++;
pp[co[i]]=1;
pa[top]=co[i];
}
tot[co[i]]+=w[i];
}
search();
cout<<ans;
return 0;
}
回复
共 4 条回复,欢迎继续交流。
正在加载回复...