为什么判了重边还是52分??枯了

P2272 [ZJOI2007] 最大半连通子图

MiaoZ @ 2019-02-27 19:27:17

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,M=1e6+5;
int n,m,X,C,K,f[N],g[N],q[N],ru[N];
int tot,top,color,s[N],dfn[N],low[N],co[N],size[N];
bool vis[N];
int cnt,fro[N],fro2[N];
struct edge{int to,nxt;}e[M],e2[M];
inline int read() {
    int x=0; char c=getchar();
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
    return x;
}
void add1(int x,int y) {
    e[++cnt]={y,fro[x]}; fro[x]=cnt;
}
void add(int x,int y) {
    e2[++cnt]={y,fro2[x]}; fro2[x]=cnt;
    ru[y]++;
}

void Tarjan(int u) {
    dfn[u]=low[u]=++tot;
    s[++top]=u;
    for(int i=fro[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if(!dfn[v]) {
            Tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!co[v]) 
         low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]) {
        co[u]=++color;
        while(s[top]!=u) {
            co[s[top--]]=color;
            size[color]++;
        }
        top--,size[color]++;
    }
}

void rebuild() {
    cnt=0;
    for(int i=1;i<=n;i++) 
     for(int j=fro[i];j;j=e[j].nxt)
      if(co[i]!=co[e[j].to]) 
       add(co[i],co[e[j].to]);
}

void DP() {
    int h=0,t=0;
    for(int i=1;i<=color;i++) {
        if(!ru[i]) q[t++]=i;
        f[i]=size[i],g[i]=1;
    }
    while(h!=t) {
        int u=q[h++],v;
        for(int i=fro2[u];i;i=e2[i].nxt) {
            ru[v=e2[i].to]--;
            if(!ru[v]) q[t++]=v;
            if(vis[v]==u) continue; //处理重边 
            if(f[u]+size[v]>f[v]) {
                f[v]=f[u]+size[v];
                g[v]=g[u];
            }
            else if(f[u]+size[v]==f[v]) 
             g[v]=(g[v]+g[u])%X;
            vis[v]=u;
        }
    }
}

int main() {
    n=read(),m=read(),X=read();
    for(int i=1;i<=m;i++) {
        int a=read(),b=read();
        add1(a,b);
    }
    for(int i=1;i<=n;i++) 
     if(!dfn[i]) Tarjan(i);
    rebuild(),DP(); cout<<endl;
    for(int i=1;i<=color;i++) {
        cout<<size[i]<<endl;
        if(f[i]>K) K=f[i],C=g[i];
        else if(f[i]==K) C=(C+g[i])%X;
    }
    printf("%d\n%d",K,C);
}

|