社区讨论

#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 条回复,欢迎继续交流。

正在加载回复...