社区讨论

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

正在加载回复...