社区讨论
WA了6个点,用的vector,哪里错了?
P3387【模板】缩点参与者 2已保存回复 9
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 9 条
- 当前快照
- 1 份
- 快照标识符
- @mi7cumxr
- 此快照首次捕获于
- 2025/11/20 19:35 4 个月前
- 此快照最后确认于
- 2025/11/20 19:35 4 个月前
CPP
#include <bits/stdc++.h>
using namespace std;
int read( ){
int x=0,y=1;
char c=getchar( );
while(c>'9'||c<'0'){if(c=='-')y=-1;c=getchar( );}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar( );}
return x*y;
}
int n,m,w[10001];
bool vis[10001];
int dfn[10001],low[10001],stac[10001],top,num=1;
int sd[10001];
vector<int> a[10001];
vector<int> b[10001];
int in[10001],dist[10001];
void tarjian(int u)
{
dfn[u]=low[u]=num;
num++;
vis[u]=1;
stac[++top]=u;
for(register int i=0;i<a[u].size( );i++)
{
int v=a[u][i];
if(!dfn[v])
{
tarjian(v);
low[u]=min(low[u],low[v]);
}
else if(vis[v]) low[u]=min(low[u],dfn[v]);
}
if (dfn[u]==low[u])
{
int v;
while (v=stac[top--])
{
sd[v]=u;
vis[v]=0;
if (u==v) break;
w[u]+=w[v];
}
}
}
int topo()
{
queue <int> q;
int tot=0;
for (register int i=1;i<=n;i++)
if (sd[i]==i&&!in[i])
{
q.push(i);
dist[i]=w[i];
}
while (!q.empty( ))
{
int u=q.front( );q.pop( );
// for (int i=h[k];i;i=ed[i].next)
for(register int i=0;i<b[u].size( );i++)
{
// int v=ed[i].to;
int v=b[u][i];
dist[v]=max(dist[v],dist[u]+w[v]);
in[v]--;
if (in[v]==0) q.push(v);
}
}
int ans=0;
for (int i=1;i<=n;i++)
ans=max(ans,dist[i]);
return ans;
}
int main( ){
freopen("1.in","r",stdin);
n=read( );m=read( );
for(register int i=1;i<=n;i++) w[i]=read( );
for(register int i=1;i<=m;i++){
int u,v;
u=read( );v=read( );
a[u].push_back(v);
}
for(register int i=1;i<=n;i++)
if(!dfn[i]) tarjian(i);
for(register int i=1;i<=n;i++)
for(register int j=0;j<a[i].size( );j++){
int u=i,v=a[i][j];
if(sd[u]!=sd[v]){
b[u].push_back(v);
in[v]++;
}
}
printf("%d",topo( ));
return 0;
}
回复
共 9 条回复,欢迎继续交流。
正在加载回复...