只有52分啊,求dolao帮忙看看!

P2272 [ZJOI2007] 最大半连通子图

可耐的菊花茶 @ 2018-07-05 09:16:04

#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 100005
#define maxe 1000005
using namespace std;
bool vis[maxn];
int n,e,tt,tim,tot,top,ans,sum,x[maxe],y[maxe],lnk[maxn],net[maxe],son[maxe];
int que[maxn],fa[maxn],ru[maxn],siz[maxn],col[maxn],stack[maxn],dfn[maxn],low[maxn],f[maxn],g[maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline int add(int x,int y){net[++tot]=lnk[x];son[tot]=y;lnk[x]=tot;}
void tarjan(int x){
    dfn[x]=low[x]=++tim;
    vis[x]=1;stack[++top]=x;
    for (int j=lnk[x];j;j=net[j])
    if (!dfn[son[j]]) tarjan(son[j]),low[x]=min(low[x],low[son[j]]);
    else if (vis[son[j]]) low[x]=min(low[x],dfn[son[j]]);
    if (dfn[x]==low[x]){
        col[0]++;
        int sum=0,now=0;
        while (now!=x){
            sum++;
            now=stack[top--];
            col[now]=col[0];
            vis[now]=0;
        }
        siz[col[0]]=sum;
    }
}
inline int get(int x){return x==fa[x]?x:fa[x]=get(fa[x]);}
void mrk_e(){
    tot=0;
    memset(lnk,0,sizeof(lnk));
    for (int i=1;i<=col[0];i++) fa[i]=i;
    for (int i=1;i<=e;i++)
    if (col[x[i]]!=col[y[i]]){
        int fx=get(col[x[i]]),fy=get(col[y[i]]);
        if (fx==fy) continue;
        fa[fx]=fy;ru[col[y[i]]]++;
        add(col[x[i]],col[y[i]]);
    }  
}
void tuopu(){
    int hed=0,tal=0;
    for (int i=1;i<=col[0];i++){
        f[i]=siz[i];g[i]=1;
        if (!ru[i]) que[++tal]=i;
    }
    while (hed!=tal){
        hed++;
        int x=que[hed];
        for (int j=lnk[x];j;j=net[j]){
            ru[son[j]]--;
            if (ru[son[j]]==0) que[++tal]=son[j];
            if (f[son[j]]<f[x]+siz[son[j]]) f[son[j]]=f[x]+siz[son[j]],g[son[j]]=g[x];
            else if (f[son[j]]==f[x]+siz[son[j]]) g[son[j]]=(g[son[j]]+g[x])%tt;
        }
    }
}
int main(){
    freopen("1093.in","r",stdin);
    freopen("1093.out","w",stdout);
    n=read();e=read();tt=read();
    for (int i=1;i<=e;i++){
        x[i]=read(),y[i]=read();
        add(x[i],y[i]);
    }
    for (int i=1;i<=n;i++)
    if (!dfn[i]) tarjan(i);
    mrk_e();
    tuopu();
    for (int i=1;i<=col[0];i++)
    if (f[i]>ans) ans=f[i],sum=g[i];
    else if (f[i]==ans) sum=(sum+g[i])%tt;
    printf("%d\n%d\n",ans,sum);
    return 0;
}

by 可耐的菊花茶 @ 2018-07-05 09:18:28

好尴尬,一不小心,dalao成了dolao。。。


by creed_ @ 2018-07-12 00:13:23

@可耐的菊花茶 这个题很坑,要注意缩点以后会出现重边,然后你再dp的时候就炸掉了。。。。。


by 可耐的菊花茶 @ 2018-07-12 08:06:00

@creed_ 可我mrk_e里面用并查集拿来判重边了啊。


by creed_ @ 2018-07-12 08:24:25

@可耐的菊花茶

并查集判重边应该是不可以的

1 2 1 3 2 4 3 4

你考虑这样一个图

前三条边加进去,3和4就已经在一个集合了

但第四条边确实也还有加的必要对吧。

所以还是排序判重好了


by creed_ @ 2018-07-12 08:24:56

@可耐的菊花茶

1 2

1 3

2 4

3 4


by 可耐的菊花茶 @ 2018-07-12 09:48:55

@creed_ 仿佛明白了什么,谢谢dalao。


|