求助88对拍了一下午没找到hack,不知道哪里错了

P2272 [ZJOI2007] 最大半连通子图

dengjunhaodejia09 @ 2023-04-18 19:24:25

#include <bits/stdc++.h>

using namespace std;
int ppt;
struct edng{
    int to,nxt;
}e[1000002];
int cnt,head[100002],color[100002];
int bbb=0,ans=0;
bool vis[100005];
int dfn[100006],low[100005],gshu[100005];
bool kun[100005];
stack <int> s;
inline int read(){
    int x=0,f=1,ch=getchar();
    for(;!isdigit(ch);ch=getchar()) f=(ch=='-')?-1:1;
    for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void dfs(int x){
    bbb++;
    vis[x]=true;
    dfn[x]=low[x]=bbb;
    s.push(x);
    for(int i=head[x];i;i=e[i].nxt){
        if(dfn[e[i].to]==false){
            dfs(e[i].to);
            low[x]=min(low[x],low[e[i].to]);
        }else if(vis[e[i].to]) low[x]=min(low[x],dfn[e[i].to]);
    }
    if(low[x]==dfn[x]){
        ans++;
        int tmp=-1;
        do{
            tmp=s.top();
            s.pop();
            color[tmp]=ans;
            vis[tmp]=0;
            gshu[ans]++;
        }while(tmp!=x);
    }
}
int hhh[100005];
int Max=INT_MIN;
int ll=0;
int AK[100005];
int aa[100005];
inline int dfs(int yanse,int sum){
    kun[yanse]=true;

    int o=0,kkk=0;
    int gg=0;
    for(int i=head[yanse];i;i=e[i].nxt){
        int rjl=e[i].to;
        if(kun[rjl]==false){
            kkk=max(kkk,dfs(rjl,sum+gshu[yanse]));
        }
        //2 3 1 4 5 6 7
        if(kun[rjl]==true){
            if(o<AK[rjl]){
                gg=aa[rjl];
                o=AK[rjl];
            }else if(o==AK[rjl]){
                gg+=aa[rjl];
            }
        }
    }
    hhh[sum+o+gshu[yanse]]+=max(gg,1);
    hhh[sum+o+gshu[yanse]]=hhh[sum+o+gshu[yanse]]%ppt;
    Max=max(sum+o+gshu[yanse],Max);
    AK[yanse]=max(o,kkk)+gshu[yanse];
    aa[yanse]=max(gg,1); 
    return o+gshu[yanse];
}
struct node{
    int xx,yy;
}hi[1000005];
int cmp(node bbc,node ccb){
    if(bbc.xx!=ccb.xx){
        return bbc.xx<ccb.xx;
    }else{
        return bbc.yy<ccb.yy;
    }
}
int cmpp(node bbc,node ccb){
    if(color[bbc.xx]!=color[ccb.xx]){
        return color[bbc.xx]<color[ccb.xx];
    }else{
        return color[bbc.yy]<color[ccb.yy];
    }
}
int main(){
    int n,m;
    cin>>n>>m>>ppt;
    for(int i=1;i<=m;i++){
        int x,y;
        hi[i].xx=read();
        hi[i].yy=read();    
    }
    sort(hi+1,hi+m+1,cmp);
    for(int i=1;i<=m;i++){
        if(hi[i].xx==hi[i-1].xx && hi[i].yy==hi[i-1].yy)continue;
        if(hi[i].xx==hi[i].yy){
            continue;
        }else{
            cnt++;
            e[cnt].to=hi[i].yy;
            e[cnt].nxt=head[hi[i].xx];
            head[hi[i].xx]=cnt;
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
    memset(head,0,(ans+1)*sizeof(int));
    memset(e,0,(m+1)*sizeof(edng));
    cnt=0;
    sort(hi+1,hi+m+1,cmpp);
    for(int i=1;i<=m;i++){

        if(color[hi[i].xx]==color[hi[i-1].xx] && color[hi[i].yy]==color[hi[i-1].yy])continue;
        if(color[hi[i].xx]==color[hi[i].yy]){
            continue;
        }else{
            cnt++;
            e[cnt].to=color[hi[i].yy];
            e[cnt].nxt=head[color[hi[i].xx]];
            head[color[hi[i].xx]]=cnt;
        }
    }
    for(int i=1;i<=ans;i++){
        int l=dfs(i,0);
    }
//  
//  for(int i=1;i<=ans;i++){
//      cout<<AK[i]<<" ";
//  }
//  cout<<endl;
    cout<<Max<<endl<<hhh[Max];
    return 0;
}

by djy123456 @ 2024-07-15 13:51:49

@dengjunhaodejia09

没%

orz


|