蒟蒻76分求助

P2272 [ZJOI2007] 最大半连通子图

Mosher @ 2019-09-03 15:41:18

第七个点,会输出0,0;

貌似在统计入度时,最后结果没有为0的

tarjan缩点下来没问题,应该问题出在build中,是我map用法有误吗???

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define ll long long
const ll maxn=4e5+5;
const ll maxm=2e6+5;
map<pair<ll,ll>,bool>mapp;
queue<ll>q;
ll dfn[maxn],low[maxn],dfs_clock,size,tot,head[maxn],n,m,col[maxn],dp[maxn],mod,sz[maxn],x[maxn],y[maxn],rd[maxn],dis[maxn],cnt[maxn],ans_id,ans;
struct node{
    ll v,nxt;
}e[maxm];

il ll read(){
    ll x=0;char a=getchar();
    while(!isdigit(a)) a=getchar();
    while(isdigit(a)) {x=x*10+a-'0';a=getchar();}
    return x;
}

il void add(ll u,ll v){
    e[++size].v=v;
    e[size].nxt=head[u];
    head[u]=size;
}

stack<ll>s;
void tarjan(ll u){
    s.push(u);
    dfn[u]=low[u]=++dfs_clock;
    for(ll i=head[u];i;i=e[i].nxt){
        ll v=e[i].v;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!col[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ll k;++tot;
        do{
            k=s.top();s.pop();
            col[k]=tot;
            sz[tot]++;
        }while(k!=u);
    }
}

il void clear(){
    size=0;
    memset(e,0,sizeof(e));
    memset(head,0,sizeof(head));
}

il void build(){
    for(ll i=1;i<=m;++i){
        int nx=col[x[i]],ny=col[y[i]];
        if(nx!=ny&&!mapp[make_pair(nx,ny)]){
            rd[ny]++;
            mapp[make_pair(nx,ny)]=1;
            add(nx,ny);
        }
    }
}

void bfs(){
    while(!q.empty()){
        ll u=q.front();q.pop();
        for(ll i=head[u];i;i=e[i].nxt){
            ll v=e[i].v;
            --rd[v];
            if(dis[v]<dis[u]+sz[v]){
                dis[v]=dis[u]+sz[v];
                cnt[v]=0;
                if(dis[ans_id]<dis[v]) ans_id=v;
            }
            if(dis[v]==dis[u]+sz[v]) cnt[v]=(cnt[v]+cnt[u])%mod;
            if(!rd[v]) q.push(v);
        }
    }
}

int main(){
    n=read();m=read();mod=read();
    for(ll i=1;i<=m;++i){
        x[i]=read();y[i]=read();
        add(x[i],y[i]);
    }
    for(ll i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
    clear();
    build();
    for(ll i=1;i<=tot;++i){
        if(!rd[i]){
            q.push(i);
            dis[i]=sz[i];
            cnt[i]=1;
            if(dis[ans_id]<dis[i]) ans_id=i;
        }
    }
    bfs();
    for(ll i=1;i<=n;++i)
        if(dis[i]==dis[ans_id]) ans=(ans+cnt[i])%mod;
    printf("%lld\n%lld",dis[ans_id],ans);
}

by Mosher @ 2019-09-03 16:01:47

此贴终结

提个醒:空间要开足够大,比如乘10倍的亚子


by Peter0721 @ 2019-09-03 17:48:57

撤离ing


|