[USACO5.3]校园网Network of Schools

传送门

这道题还是比较容易看出是tarjan的。首先我们知道如果学校之间成环的话那么学校之间一定能到达，直接缩成一个点就好了。

缩完点之后我们得到了一个DAG。之后因为子任务A要求的是最少接受新软件的学校有多少个，可以很容易的想出我们只要给所有入度为0的学校发一份就可以了，因为剩下的必然是可以从其他学校传过来的嘛。

子任务A的答案就是DAG中入度为0的点数。

至于子任务2，我们要求的就是把这个图变为强连通分量至少要加几条边。思考之后发现，一个点如果入度为0，那么它就无法被其他学校传进来，那么就不行，然后如果一个点出度为0，他就无法传出，也不行。所以我们直接统计一下入度为0和出度为0的点数，两者最大值则为结果。（因为我们至少要保证所有点都有至少一个入度和出度，最优策略就是把入度为0和出度为0的点连边，剩下的随便连即可，所以是最大值）

然后如果整个图全都在一个强连通分量中，需要进行特判（会认为当前的DAG没有出度）

看一下代码。

#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> #include<cmath> #include<queue> #include<set> #include<map> #define rep(i,a,n) for(int i = a;i <= n;i++) #define per(i,n,a) for(int i = n;i >= a;i--) #define enter putchar('\n')using namespace std; typedef long long ll; const int M = 50005;int read() {int ans = 0,op = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-') op = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){ans *= 10;ans += ch - '0';ch = getchar();}return ans * op; }struct edge {int next,to,from; }e[M<<2],e1[M<<2]; int n,m,cnt,ecnt,cur,low[M],dfn[M],stack[M],top,curr,vis[M],belong[M],head[M],ecnt1,head1[M]; int rdeg[M],cdeg[M],sum1,sum2,tot; bool in[M],pd[M];void add(int x,int y) {e[++ecnt].to = y;e[ecnt].next = head[x];e[ecnt].from = x;head[x] = ecnt; }void tarjan(int x) {dfn[x] = low[x] = ++cnt;in[x] = 1,stack[++top] = x;for(int i = head[x];i;i = e[i].next){if(!dfn[e[i].to]) tarjan(e[i].to),low[x] = min(low[x],low[e[i].to]);else if(in[e[i].to]) low[x] = min(low[x],dfn[e[i].to]);}if(low[x] == dfn[x]){int p;while(p = stack[top--]){belong[p] = x,in[p] = 0;pd[x] = 1;if(p == x) break;}} } void rebuild() {rep(i,1,ecnt){int r1 = belong[e[i].to],r2 = belong[e[i].from];if(r1 != r2){e1[++ecnt1].to = r1;e1[ecnt1].from = r2;e1[ecnt1].next = head1[r2];head1[r2] = ecnt1;rdeg[r1]++,cdeg[r2]++;}} }int main() {n = read();rep(i,1,n){while(1){m = read();if(!m) break;add(i,m);}}rep(i,1,n) if(!dfn[i]) tarjan(i);rebuild();rep(i,1,n){if(!pd[i]){curr++;continue;}if(!rdeg[i]) sum1++;if(!cdeg[i]) sum2++;}printf("%d\n",sum1);if(curr == n-1) printf("0\n");else printf("%d\n",max(sum1,sum2));return 0; }

 

转载于:https://www.cnblogs.com/captain1/p/9680827.html

总结

以上是生活随笔为你收集整理的[USACO5.3]校园网Network of Schools的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。