请大佬捉鱼

P2272 [ZJOI2007] 最大半连通子图

Plus_Ultra @ 2019-08-20 09:22:00

到底是哪儿错了。。。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>

#define MAXN 1000010

using namespace std;

int edge[2*MAXN],nxt[2*MAXN],head[MAXN],tot,n,m,mod;
int dfn[MAXN],low[MAXN],scc[MAXN],in[MAXN],cnt,ti;
stack<int> S;
queue<int> q;
int x[MAXN],y[MAXN],b[MAXN],rdu[MAXN];
int dis[MAXN],ans,sum,e[MAXN];

void add(int x,int y)
{
    edge[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}

void tarjan(int x)
{
    dfn[x]=low[x]=++ti;
    S.push(x);
    for(int i=head[x];i;i=nxt[i])
    {
        int y=edge[i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else  if(!scc[y])  low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        scc[x]=++cnt;in[cnt]++;
        while(S.top()!=x)
        {
            int y=S.top();
            scc[y]=cnt;
            in[cnt]++;
            S.pop();
        }
        S.pop();
    }
}

bool cmp(int a,int l)
{
    if(x[a]==x[l])  return y[a]<y[l];
    return x[a]<x[l];
}

void pre()
{
    for(int i=1;i<=m;i++)
        b[i]=i,x[i]=scc[x[i]],y[i]=scc[y[i]];//???b[i]=i
    sort(b+1,b+m+1,cmp);//x+1,x+m+1
}

void build()
{
    tot=0;
    memset(head,0,sizeof(head));
    for(int k=1;k<=m;k++)
    {
        int i=b[k];//?
        if(x[i]!=y[i]&&(x[i]!=x[b[k-1]]||y[i]!=y[b[k-1]]))//(x[i]!=x[i-1]||y[i]!=y[i-1])
            add(x[i],y[i]),rdu[y[i]]++;
    }
}

void topsort()
{
    for(int i=1;i<=cnt;i++)
        if(!rdu[i])  
        {
            e[i]=1;
            dis[i]=in[i];
            q.push(i);
            if(dis[ans]<dis[i])  ans=i;//?
        }  
    while(q.size())
    {
        int x=q.front();
        for(int i=head[x];i;i=nxt[i])
        {
            int y=edge[i];rdu[y]--;
            if(dis[y]<dis[x]+in[y])//+in[x]
            {
                dis[y]=dis[x]+in[y];//+in[x]
                e[y]=0;
                if(dis[y]>dis[ans])  ans=y;
            }
            if(dis[y]==dis[x]+in[y])//+in[x]
            {
                e[y]=(e[y]+e[x])%mod;
                if(!rdu[y])  q.push(y);//if(!(--rdu[y]))
            }
        }
    }
}

int main()
{
    cin>>n>>m>>mod;
    for(int i=1;i<=m;i++)  
    {
        cin>>x[i]>>y[i];
        add(x[i],y[i]);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i])  tarjan(i);

    pre();
    build();
    topsort();

    for(int i=1;i<=n;i++)
        if(dis[i]==dis[ans])  sum=(sum+e[i])%mod;

    cout<<dis[ans]<<endl<<sum<<endl; //ans,sum

    return 0;
}

by Plus_Ultra @ 2019-08-20 09:53:53

改了q.pop()后64分。。。


by Plus_Ultra @ 2019-08-20 10:22:39

结帖


|