题解 P2341 【[HAOI2006]受欢迎的牛】

2017-10-04 22:13:26


记忆化搜索+Tarjan

首先我们想想暴力: $O[N(N+m)]$ 显然炸了

于是想到强连通分量:题目给出的是一个等价关系,而显然同一个SCC里面的奶牛都可达,于是我们先缩点,同时记录每个点包括多少奶牛,再取反图,这样问题就变成了找一个点可以到所有点。

整张图现在是个DAG,于是我们可以证明:此时只有一个点满足其他点都可以到达。

证明: 假设存在两个这样的点A和B,那么由于其他点都可以到A,自然B也可以到A;同理A也可以到B,因此A和B应该属于同一个强连通分量。但是它们在缩点后是两个点,与上述矛盾,于是假设不成立,不存在两个点,满足其他所有店都可以到它们。

既然是DAG,不妨设$f(i):$由i可以到几个点(包括i),直接记忆化搜索即可。注意判断:如果图上能到的点的数目最大值都没有达到SCC数目,要输出0.

复杂度:$O(N+M)$

附代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <stack>
#include <algorithm>
using namespace std;
const int MAXN = 10000, MAXM = 50000;
struct Edge{
    int v,next;
};
struct AdjTable{
    int e_ptr=1,head[MAXN+10];
    Edge E[MAXM*2+10];
    void addedge(int u,int v){
        E[e_ptr]=(Edge){v,head[u]};head[u]=e_ptr++;
    }
}; 
inline int readint() {
    register int f=1,r=0;
    register char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1; c=getchar();}
    while(isdigit(c)){r=r*10+c-'0'; c=getchar();}
    return f*r;
}

int N,M,maxp,maxv,W[MAXN+10],scc_cnt,dfs_clock,dfn[MAXN+10],low[MAXN+10],sccno[MAXN+10],opt[MAXN+10];
stack<int> S; AdjTable G1,G2; 

void dfs(int u) {
    low[u]=dfn[u]=++dfs_clock;
    S.push(u);
    for(int j=G1.head[u];j;j=G1.E[j].next) {
        int v=G1.E[j].v;
        if(!dfn[v]) {
            dfs(v); low[u]=min(low[u],low[v]);
        } else if(!sccno[v]) 
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]) {
        ++scc_cnt;
        int v;
        do {
            v=S.top();
            sccno[v]=scc_cnt;
            W[scc_cnt]++;
            S.pop();
        } while(u!=v);//!
    }
}

void Tarjan(){
    for(int i=1;i<=N;i++)
        if(!dfn[i]) dfs(i);
}

void Rebuild() {
    for(int u=1;u<=N;u++) {
        for(int j=G1.head[u];j;j=G1.E[j].next) {
            int v=G1.E[j].v;
            if(sccno[u]!=sccno[v])
                G2.addedge(sccno[v],sccno[u]);
        }
    }
}

int dp(int u) {
    if(opt[u]>0) return opt[u];
    opt[u]=1;
    for(int j=G2.head[u];j;j=G2.E[j].next) {
        int v=G2.E[j].v;
        opt[u]+=dp(v);
    }
    return opt[u];
}

int main() {
    N=readint(); M=readint();
    for(int i=1;i<=M;i++) {
        int a,b;a=readint();b=readint();
        G1.addedge(a,b);
    }
    Tarjan(); 
    Rebuild();
    for(int i=1;i<=scc_cnt;i++)
        if(dp(i)>maxv) {
            maxv=dp(i);maxp=i;
        }
    if(maxv == scc_cnt)
        printf("%d",W[maxp]);
    else printf("0");
}