dag上dp-1

斗神_君莫笑 · 2019-09-13 09:47:01 · 题解

对于本题，最大的难点就在于怎么求出一条边的路径数
第一次做的时候我只考虑了前驱，然而现实是还要考虑后继
每条边经过的路径数是前驱*后继（归到点上）
因此建两张正反图，分别处理出到每个点的路径数就可以了
顺便吐槽一句数据真水

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int u,v,w,nxt;
}e[100010],a[100010];
int head[5010],cnt;
void add(int u,int v){
    e[++cnt].u=u;
    e[cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
int head1[5010],cnt1;
void add1(int u,int v){
    a[++cnt1].u=u;
    a[cnt1].v=v;
    a[cnt1].nxt=head1[u];
    head1[u]=cnt1;
}
int ru[5010],kind[5010],st[5010];
void dfs(int u){
    for(int i=head[u];i;i=e[i].nxt){
        int v=e[i].v;
        kind[v]+=kind[u];
        ru[v]--;
        if(!ru[v])dfs(v);
    }
}
int chu[5010],kind1[5010];
void dfs1(int u){
    for(int i=head1[u];i;i=a[i].nxt){
        int v=a[i].v;
        kind1[v]+=kind1[u];
        chu[v]--;
        if(!chu[v])dfs1(v);
    }
}

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);add1(v,u);
        ru[v]++;chu[u]++;
    }
    for(int i=1;i<=n;++i)
        if(ru[i]==0)
            st[i]=1;
    for(int i=1;i<=n;++i)
        if(st[i]){
            kind[i]=1;
            dfs(i);
        }
    memset(st,0,sizeof(st));
    for(int i=1;i<=n;++i)
        if(chu[i]==0)
            st[i]=1;
    for(int i=1;i<=n;++i)
        if(st[i]){
            kind1[i]=1;
            dfs1(i);
        }
    int maxx=0;
    //for(int i=1;i<=m;++i)
    //  printf("%d\n",e[i].w);
    for(int i=1;i<=m;++i)
        maxx=max(maxx,kind[e[i].u]*kind1[e[i].v]);
    printf("%d",maxx);
    return 0;
}