P2812 校园网络
题目背景
浙江省的几所OI强校的神犇发明了一种人工智能，可以AC任何题目，所以他们决定建立一个网络来共享这个软件。但是由于他们脑力劳动过多导致全身无力身体被♂掏♂空，他们来找你帮助他们。
题目描述
共有n所学校（n<=10000）已知他们实现设计好的网络共m条线路，为了保证高速，网络是单向的。现在请你告诉他们至少选几所学校作为共享软件的母机母鸡，能使每所学校都可以用上。再告诉他们至少要添加几条线路能使任意一所学校作为母机母鸡都可以使别的学校使用上软件。
输入输出格式
输入格式：
第一行一个整数n。
接下来n行每行有若干个整数，用空格空格隔开。
第i-1行的非零整数x，表示从i到x有一条线路。以0作为结束标志。
输出格式：
第一行一个整数表示问题1的答案。
第二行回答问题2.
输入输出样例
输入样例#1： 复制
5
2 0
4 0
5 0
1 0
0
输出样例#1： 复制
2
2
说明
POJ原题。数据扩大了100倍。
其实这是两个题
P2746 [USACO5.3]校园网Network of Schools
题目描述
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 B 在 A 学校的分发列表中， A 也不一定在 B 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
输入输出格式
输入格式：
输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。
接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。
输出格式：
你的程序应该在输出文件中输出两行。
第一行应该包括一个正整数：子任务 A 的解。
第二行应该包括子任务 B 的解。
输入输出样例
输入样例#1： 复制
5
2 4 3 0
4 5 0
0
0
1 0
输出样例#1： 复制
1
2
说明
题目翻译来自NOCOW。
USACO Training Section 5.3
这两个题数据一个赛一个水
我这个应该是非正解（错误解法）
但是第二个题得了九十分
第一个题得了100分
还说在POJ的基础上数据扩大了100倍
怎么还是这么水
#include<iostream>
#include<cstring>
#include<cstdio>
#define N 10005
using namespace std;
struct Edge{
int v,nxt;
}e[N];
int head[N],tot;
int top;
int col[N];
int n,m,ans;
int vis[N],sta[N];
int dfn[N],low[N];
int col_num,dfn_num;
void addEdge(int a,int b){
e[++tot].v=b;
e[tot].nxt=head[a];
head[a]=tot;
}
void Tarjan(int x){
dfn[x]=low[x]=++dfn_num;
sta[++top]=x;
vis[x]=true;
for(int i=head[x];i;i=e[i].nxt){
int to=e[i].v;
if(!dfn[to]){
Tarjan(to);
low[x]=min(low[x],low[to]);
}
else if(vis[to])
low[x]=min(low[x],dfn[to]);
}
if(dfn[x]==low[x]){
vis[x]=false;
col[x]=++col_num;
while(sta[top]!=x){
col[sta[top]]=col_num;
vis[sta[top]]=false;
top--;
}
top--;
}
}
int to;
int Ru[N];
int Chu[N];
int main(){
while(~scanf("%d",&n)){
for(int i=1;i<=n;++i){
scanf("%d",&to);
while(to){
addEdge(i,to);
scanf("%d",&to);
}
}
int a,b;a=b=0;
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].nxt){
to=e[j].v;
if(col[i]!=col[to]){
Chu[col[i]]++;
Ru[col[to]]++;
}
}
for(int i=1;i<=col_num;++i){
if(!Chu[i])
b++;
if(!Ru[i])
a++;
}
if(col_num==1)b=0;
printf("%d
%d
",a,b);
}
return 0;
}
看了题解才知道我距离正解只有一步之遥
还是太年轻，考虑问题不够全面
Tarjan缩点 对缩点后新图扫每个强连通块的入度出度
对于子任务A 求需要给多少个学校发软件 即为求有多少个入度为0的点 因为对于对于每个入度不为0的点一定可以从一个其他点走到
对于子任务B 求入度为0的点个数与出度为0的点个数的最大值 需要添多少条边才能形成使所有点都可以被某个点到达 所以对于每个出度为0的点 需要拓展一条出边 对于每个入度为0的点 需要拓展一条入边 为了减少拓展边数 可以将所有出度为0的点拓展出边到某个入度为0的点的上 最后答案即为 max（入度为0点数，出度为0点数）