题解 P2341 【[HAOI2006]受欢迎的牛】
panda_2134
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)$
附代码：
```cpp
#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");
}
```