社区讨论
偷鸡偷不成,被hack数据制裁了
P3387【模板】缩点参与者 2已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @m448diui
- 此快照首次捕获于
- 2024/11/30 21:51 去年
- 此快照最后确认于
- 2025/11/04 13:33 4 个月前
CPP
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=10005,M=100005;
int n,m,u,v,scc[N],cnt,low[N],dfn[N],tot,din[N],dout[N],t[N],siz[N],ans;
int sta[N],top;
bool insta[N];
vector<int>e[N],e1[N];
void tarjan(int x){
low[x]=dfn[x]=++tot;
insta[x]=true;
sta[++top]=x;
for(int y:e[x]){
if(!dfn[y]){
tarjan(y);
low[x]=min(low[x],low[y]);
}else if(insta[y]){
low[x]=min(low[x],dfn[y]);
}
}
if(low[x]==dfn[x]){
int y;
++cnt;
do{
y=sta[top--];
insta[y]=false;
scc[y]=cnt;
siz[cnt]+=t[y];
}while(x!=y);
}
}
int dfs(int u){
bool vis[N]={};
int an=0;
for(int y:e1[u]){
if(!vis[y]){
vis[y]=true;
an=max(an,dfs(y));
}
}
return an+siz[u];
}
int main(){
//ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&t[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
e[u].push_back(v);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
for(int x=1;x<=n;x++){
for(int y:e[x]){
if(scc[x]!=scc[y]){
e1[scc[x]].push_back(scc[y]);
}
}
}
for(int i=1;i<=cnt;i++) ans=max(ans,dfs(i));
printf("%d",ans);
return 0;
}
回复
共 2 条回复,欢迎继续交流。
正在加载回复...