P2746 [USACO5.3]校园网Network of Schools// POJ1236: Network of Schools
题目描述
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 B 在 A 学校的分发列表中， A 也不一定在 B 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
输入输出格式
输入格式：
输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。
接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。
输出格式：
你的程序应该在输出文件中输出两行。
第一行应该包括一个正整数：子任务 A 的解。
第二行应该包括子任务 B 的解。
输入输出样例
输入样例#1： 复制
52 4 3 04 5 0001 0
输出样例#1： 复制
12
说明
题目翻译来自NOCOW。
USACO Training Section 5.3
解题报告：
题目大意：给定一个有向图，求1.至少要选几个点，可以到达全部的点，2.至少要连几条边，使得整个图是强联通的（即从任意一个顶点出发，可以到达任意一个顶点）
有用的定理:有向无环图中所有入度不为0的点，一定可以由某个入度为0的点出发可达。 (由于无环，所以从任何入度不为0的点往回走，必然终止于一个入度为0的点)
思路：tarjan缩点，求出入度为0的点的个数，即为1的答案；
在DAG上要加几条边，才能使得DAG变成强连通的，问题2的答案就是多少，
加边的方法：要为每个入度为0的点添加入边，为每个出度为0的点添加出边
假定有 n 个入度为0的点，m个出度为0的点， max(m,n)就是第二个问题的解(证明难，略）
#include<iostream>#include<queue>#include<cstdio>#include<cstring>#include<algorithm>#include<stack>#include<vector>#define N 2000000using namespace std;void in(int &x){ ???register char c=getchar();x=0;int f=1; ???while(!isdigit(c)){if(c==‘-‘) f=-1;c=getchar();} ???while(isdigit(c)){x=x*10+c-‘0‘;c=getchar();} ???x*=f;}int ans1,ans2,n,tot,head[N];struct node{ ???int to,next;}e[N];int dfn[N],low[N],cnt,item,belong[N],rd[N],cd[N];stack<int>S;bool vis[N];void tarjan(int u){ ???dfn[u]=low[u]=++item; ???vis[u]=1;S.push(u); ???for(int i=head[u];i;i=e[i].next){ ???????int v=e[i].to; ???????if(!dfn[v]){ ???????????tarjan(v); ???????????low[u]=min(low[u],low[v]); ???????}else if(vis[v]) low[u]=min(low[u],dfn[v]); ???}if(low[u]==dfn[u]){ ???????int v=u;++cnt; ???????do{ ???????????v=S.top();S.pop(); ???????????vis[v]=0;belong[v]=cnt; ???????}while(v!=u); ???}}void add(int u,int v){ ???e[++tot].to=v,e[tot].next=head[u],head[u]=tot;}int main(){ ???in(n); ???for(int x,i=1;i<=n;i++){ ???????while(1){ ???????????in(x); ???????????if(!x) break; ???????????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=head[i];j;j=e[j].next){ ???????????int v=e[j].to; ???????????if(belong[i]!=belong[v]){ ???????????????rd[belong[v]]++; ???????????????cd[belong[i]]++; ???????????} ???????} ???}for(int i=1;i<=cnt;i++){ ???????if(!rd[i]) ++ans1; ???????if(!cd[i]) ++ans2; ???}ans2=max(ans1,ans2); ???if(cnt==1) ans2=0; ???printf("%d\n%d",ans1,ans2); ???return 0;}洛谷P2812是这题的加强版，可以顺便A掉
P2746 [USACO5.3]校园网Network of Schools// POJ1236: Network of Schools
原文地址：https://www.cnblogs.com/song-/p/9545939.html