题解 P2746 【[USACO5.3]校园网Network of Schools】

kradcigam

2020-05-01 22:32:06

Solution

## 之前的bug现已修复 # 前置知识: - [强联通分量](https://blog.csdn.net/qq_46230164/article/details/105406699) # 分析 这道题的话,我们先考虑缩点。 不会缩点的可以看一下我的[文章](https://blog.csdn.net/qq_46230164/article/details/105406699) 既然我们缩好点了,那么整张图变成了一个 $DAG$(有向无环图) 这样就好处理了。 - 对于问题 `A` 我们发现既然这整张图是 $DAG$,那么答案显然为入度为 $0$ 的点的个数 - 对于问题 `B` 我们发现这整张图是 $DAG$。我们要把它变成连通图。 连通图需要满足: - 没有入度为 $0$ 的点 - 没有出度为 $0$ 的点 考虑入度为 $0$ 和 出度为 $0$ 的点两两匹配,则需要匹配 $\max\{ \texttt{入度为}\ 0\ \texttt{的点},\texttt{入度为}\ 1\ \texttt{的点}$ 次。 # 一些细节 注意缩点后只有一个点的情况,本身就是连通的,所以 问题 `B` 的答案为 $0$ ```cpp #include <bits/stdc++.h> using namespace std; template<typename T>inline void read(T &FF){ T RR=1;FF=0;char CH=getchar(); for(;!isdigit(CH);CH=getchar())if(CH=='-')RR=-1; for(;isdigit(CH);CH=getchar())FF=(FF<<1)+(FF<<3)+(CH^48); FF*=RR; } template<typename T>inline void write(T x){ if(x<0)putchar('-'),x=-x; if(x>9)write(x/10); putchar('0'+x%10); } const int MAXN=1e6+10,MAXM=1e6+10; int s[MAXN],stop,dfn[MAXN],low[MAXN],scccnt,sccnum[MAXN],dfscnt,tot,he[MAXN],ne[MAXM<<1],ed[MAXM<<1],n,x,se,es,du[MAXN],ud[MAXN]; void add(int x,int y){ ed[++tot]=y; ne[tot]=he[x]; he[x]=tot; } inline void tarjan(int now){ dfn[now]=low[now]=++dfscnt; s[stop++]=now; for (int i=he[now];i;i=ne[i]){ if(!dfn[ed[i]]){ tarjan(ed[i]); low[now]=min(low[now],low[ed[i]]); }else if(!sccnum[ed[i]]){ low[now]=min(low[now],dfn[ed[i]]); } } if(dfn[now]==low[now]){ scccnt++; do{ sccnum[s[--stop]]=scccnt; }while(s[stop]!=now); } }//tarjin的板子 int main(){ read(n); for(int i=1;i<=n;i++) while(cin>>x&&x)add(i,x); for(int i=1;i<=n;i++) if(!dfn[i])tarjan(i); for(int i=1;i<=n;i++) for(int j=he[i];j;j=ne[j]) if(sccnum[i]!=sccnum[ed[j]]){ du[sccnum[ed[j]]]++;//统计 ud[sccnum[i]]++;//统计 } for(int i=1;i<=scccnt;i++){ if(!du[i])se++;//入度为0的点 if(!ud[i])es++;//出度为0的点 } cout<<se<<endl<<(scccnt==1?0:max(se,es));//小细节 return 0; } ```