P2812 校园网络【[USACO]Network of Schools加强版】
斯德哥尔摩
2018-09-29 21:00:37
[P2812 校园网络【[USACO]Network of Schools加强版】](https://www.luogu.org/problemnew/show/P2812)
这个题有个弱化版：[P2746 [USACO5.3]校园网Network of Schools](https://www.luogu.org/problemnew/show/P2746)
首先，$Tarjan$强连通分量，然后缩点，没的说。。。
缩点以后，可以保证图里没有环，只有链。
由于不存在环，每条链必然存在一个唯一的入度为$0$的点。
显然，对于每条链，只需要将软件发给这个入度为$0$的点，就可以间接传给这条链上所有的点。
因此，$\text{任务A}$就转化为了求缩点后的图中有多少个点入度为$0$。
那，$\text{任务B}$呢？
我们发现，图中只要存在入度为$0$的点和出度为$0$的点就永远不可能满足要求：“ 不论我们给哪个学校发送新软件，它都会到达其余所有的学校 ”。
我们还发现，只要在入度为$0$的点和出度为$0$的点之间连一条边，就可以同时消灭两个“不合法”的点。
如果不能做到刚好两两配对（不妨假设入度为$0$的点多），就给每个多出来的入度为$0$的点随便找一个出度为$0$的点配对（也就是说一个点可以同时配多个点）。
因此，入度为$0$的点数与出度为$0$的点数的较大值即为$\text{任务B}$的答案。
弱化版直接交代码都可以，反正思路都一样。。。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 10010
#define MAXM 5000010
using namespace std;
int n,c=1;
int head[MAXN],indegree[MAXN],outdegree[MAXN];
int d=1,top=1,s=0;
int cstack[MAXN],deep[MAXN],low[MAXN],colour[MAXN];
bool vis[MAXN];
struct Edge{
int next,to;
}a[MAXM];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
inline void add(int x,int y){
a[c].to=y;a[c].next=head[x];head[x]=c++;
}
void dfs(int x){
deep[x]=low[x]=d++;
vis[x]=true;
cstack[top++]=x;
for(int i=head[x];i;i=a[i].next){
int v=a[i].to;
if(!deep[v]){
dfs(v);
low[x]=min(low[x],low[v]);
}
else if(vis[v])low[x]=min(low[x],deep[v]);
}
if(low[x]==deep[x]){
s++;
do{
colour[cstack[top-1]]=s;
vis[cstack[top-1]]=false;
}while(cstack[--top]!=x);
}
}
void work(){
if(s==1){
printf("1\n0\n");
return;
}
int inans=0,outans=0;
for(int i=1;i<=s;i++){
if(!outdegree[i])outans++;
if(!indegree[i])inans++;
}
printf("%d\n%d\n",inans,max(inans,outans));
}
void init(){
int x;
n=read();
for(int i=1;i<=n;i++){
x=read();
while(x!=0){
add(i,x);
x=read();
}
}
for(int i=1;i<=n;i++)if(!deep[i])dfs(i);
for(int i=1;i<=n;i++){
for(int j=head[i];j;j=a[j].next){
int v=a[j].to;
if(colour[i]!=colour[v]){
indegree[colour[v]]++;
outdegree[colour[i]]++;
}
}
}
}
int main(){
init();
work();
return 0;
}
```