题解 P2746 【[USACO5.3]校园网Network of Schools】
sukimo
2020-06-06 21:57:29
思路比较经典，先用tarjan算法缩点得到一个DAG。第一个子任务只需统计DAG中入度为$0$的点的个数即为答案，因为如果某点入度为$0$，则只能自己先接收新软件；不为$0$，则可以由其他学校分发。第二个问题稍微复杂一点，如果该DAG已经强连通，则结果为$0$，很显然；否则将入度为$0$的点数设为$x$，出度为$0$的点数设为$y$，则结果为$max\{x,y\}$。为什么呢？首先，一个强连通图必须保证不含出度和入度为$0$的点，否则不符合定义；所以说我们要把这$x+y$个点进行连接。然后一个出度为$0$的点可以和一个入度为$0$的点连一条边，这样就互补了，且尽量最少。但是很明显，有$\mid x-y\mid$个点无法互补，这样就把它们任意和其他点连边，最终结果正是$max\{x,y\}$。
代码：
```
#include<bits/stdc++.h>
using namespace std;
stack<int>stk;bool in_stk[105],flag=1;int n,edge_cnt,ind,in[105],out[105],low[105],mark[105],fir[105],order[105];struct STR{int next,to;}edge[10005];
void add(int u,int v){
edge[++edge_cnt].next=fir[u];fir[u]=edge_cnt;edge[edge_cnt].to=v;
}
void tarjan(int x){
order[x]=low[x]=++ind;in_stk[x]=1;stk.push(x);
for(int i=fir[x];i;i=edge[i].next)
if(!order[edge[i].to]){
tarjan(edge[i].to);low[x]=min(low[x],low[edge[i].to]);
}
else if(in_stk[edge[i].to])low[x]=min(low[x],order[edge[i].to]);
if(order[x]==low[x]){
int rem,node_cnt=0;
do{
rem=stk.top();node_cnt++;mark[rem]=x;in_stk[rem]=0;stk.pop();
}while(rem!=x);
if(node_cnt==n)flag=0;
}
}
int main(){
int in_0=0,out_0=0;scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int v;;){scanf("%d",&v);if(!v)break;add(i,v);}
for(int i=1;i<=n;i++)if(!order[i])tarjan(i);
for(int i=1;i<=n;i++)
for(int j=fir[i];j;j=edge[j].next)
if(mark[i]!=mark[edge[j].to]){out[mark[i]]++;in[mark[edge[j].to]]++;}
for(int i=1;i<=n;i++)
if(mark[i]==i){if(!in[i])in_0++;if(!out[i])out_0++;}
printf("%d\n%d",in_0,flag?max(in_0,out_0):0);
return 0;
}
```