[ZJOI2007]最大半连通子图 (Tarjan缩点,拓扑排序,DP)

题目链接

Solution

大概是个裸题.

可以考虑到,如果原图是一个有向无环图,那么其最大半联通子图就是最长的一条路.

于是直接 \(Tarjan\) 缩完点之后跑拓扑序 DP就好了.

同时由于是拓扑序DP,要去掉所有的重边.

Code

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=100008;

struct sj{int to,next;}a[maxn*10];

ll mod,dfn[maxn],low[maxn];

ll head[maxn],belong[maxn];

ll du[maxn],w[maxn],v[maxn];

ll tot,sta[maxn],top,size,cnt;

ll num,n,m;

ll f[maxn],js[maxn],ans,ans_siz;

struct kk{int to,fr;}cc[maxn*10];

ll read()

{

    char ch=getchar(); ll f=1,w=0;

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();}

    return f*w;

}

void add(int x,int y)

{

    a[++size].to=y;

    a[size].next=head[x];

    head[x]=size;

}

void tarjan(int x)

{

    dfn[x]=low[x]=++tot;

    sta[++top]=x;

    v[x]=1;

    for(int i=head[x];i;i=a[i].next)

    {

        int tt=a[i].to;

        if(!dfn[tt]){

          tarjan(tt);

          low[x]=min(low[x],low[tt]);

        }

        else if(v[tt]) low[x]=min(low[x],dfn[tt]);

    }

    if(dfn[x]==low[x])

    {

      belong[x]=++cnt;

      v[x]=0;

      do{

        w[cnt]++;

        belong[sta[top]]=cnt;

        v[sta[top]]=0;

      }while(sta[top--]!=x);

    }

}

bool cmp(kk x,kk y)

{

     if(x.fr==y.fr)return x.to<y.to;

     else return x.fr<y.fr;

}

void work()

{

    queue<int>q;

    for(int i=1;i<=cnt;i++)

    if(!du[i])

    q.push(i),v[i]=1,f[i]=w[i],js[i]=1;

    while(!q.empty())

    {

        int x=q.front(); q.pop();

        for(int i=head[x];i;i=a[i].next)

        {

            int tt=a[i].to;

            du[tt]--;

            if(!du[tt]&&!v[tt])q.push(tt),v[tt]=1;

            if(f[tt]==w[tt]+f[x])

            js[tt]+=js[x],js[tt]%=mod;

            if(f[tt]<w[tt]+f[x])

            {

                f[tt]=w[tt]+f[x];

                js[tt]=js[x]%mod;

            }

        }

    }

}

int main()

{

    n=read(); m=read(); mod=read();

    for(int i=1;i<=m;i++)

    add(read(),read());

    for(int i=1;i<=n;i++)

    if(!dfn[i])tarjan(i);

    for(int x=1;x<=n;x++)

    for(int i=head[x];i;i=a[i].next)

    {

        int tt=a[i].to;

        if(belong[tt]!=belong[x])

        cc[++num].fr=belong[x],cc[num].to=belong[tt];

    }

    memset(a,0,sizeof(a));

    memset(head,0,sizeof(head));

    size=0;

    sort(cc+1,cc+num+1,cmp);

    for(int i=1;i<=num;i++)

    {

      if(cc[i].fr==cc[i-1].fr&&cc[i].to==cc[i-1].to)continue;

      add(cc[i].fr,cc[i].to),du[cc[i].to]++;

    }

    work();

    for(int i=1;i<=cnt;i++)

    if(f[i]>ans)

        ans=f[i],ans_siz=js[i];

      else if(f[i]==ans)

        ans_siz+=js[i],ans_siz%=mod;

    cout<<ans<<endl<<(ans_siz+mod)%mod<<endl;

    return 0;

}

巴特西

[ZJOI2007]最大半连通子图 (Tarjan缩点,拓扑排序,DP)

题目链接

Solution

Code

最新文章

热门文章