P2746 [USACO5.3]校园网Network of Schools [tarjan缩点]

题目描述

一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使

你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

输入格式

输入文件的第一行包括一个正整数

接下来

输出格式

你的程序应该在输出文件中输出两行。

第一行应该包括一个正整数，表示子任务 A 的解。

第二行应该包括一个非负整数，表示子任务 B 的解。

输入输出样例

输入 #1

输出 #1

1
2

说明/提示

题目翻译来自NOCOW。

USACO Training Section 5.3

思路

　　由题意:

　　第一问: 显然对于每个学校能到达的点都应该染成用一种颜色, 换句话说, 就是求多少个入度为 0 的学校.

　　第二问: 至少连几条边使得全部的点强连通, 换句话说, 要使得所有点出入度都不为0.

　　因为有环的存在, 可以考虑直接缩点, 然后统计各强连通块的出入度, 为了使所有点出入度不为0, 只需取入度为0和出度为0的最大值即可.

CODE

  1 #include <bits/stdc++.h>
  2 #define dbg(x) cout << #x << "=" << x << endl
  3 
  4 using namespace std;
  5 typedef long long LL;
  6 const int maxn = 1e5 + 7;
  7 
  8 int head[maxn], dfn[maxn], low[maxn], st[maxn];
  9 int cnt = 0, tot = 0, tim = 0, top = 1, n, cl = 0;
 10 int vis[maxn];
 11 int color[maxn];
 12 int ans[maxn];
 13 int nxt[maxn];
 14 int circle_size[maxn];
 15 int cas[maxn][5];
 16 int in[maxn];
 17 int out[maxn];
 18 
 19 /*
 20 head[],结构体edge:存边
 21 
 22 dfn[],low[]:tarjan中数组
 23 
 24 st[]:模拟栈
 25 
 26 out[]:出边
 27 
 28 sd[]:强连通分量存储
 29 
 30 dq[]:统计答案
 31 */
 32 
 33 template<class T>inline void read(T &res)
 34 {
 35     char c;T flag=1;
 36     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
 37     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
 38 }
 39 
 40 struct Edge{
 41     int nxt, to;
 42 }edge[maxn * 2];
 43 
 44 inline void BuildGraph(int from, int to)
 45 {
 46     cnt++;
 47     edge[cnt].to = to;
 48     edge[cnt].nxt = head[from];
 49     head[from] = cnt;
 50 }
 51 
 52 void tarjan(int x)
 53 {
 54     tim++;
 55     dfn[x] = low[x] = tim;
 56     st[top] = x;
 57     top++;
 58     vis[x] = 1;
 59     for(int i = head[x] ; i != 0; i = edge[i].nxt)
 60     {
 61         int u = edge[i].to;
 62         if(vis[u] == 0)
 63         {
 64             tarjan(u);
 65             low[x] = min(low[x],low[u]);
 66         }
 67         else if(vis[u] == 1)
 68                 low[x] = min(low[x],dfn[u]);
 69     }
 70     if(dfn[x] == low[x])
 71     {
 72         cl++;
 73         do
 74         {
 75             top--;
 76             color[st[top]] = cl;
 77             vis[st[top]] = -1;
 78         }while( st[top] != x );
 79     }
 80     return ;
 81 }
 82 
 83 int main()
 84 {
 85     scanf("%d",&n);
 86     int q = 1;
 87     for ( int i = 1; i <= n; ++i ) {
 88         int x;
 89         while(scanf("%d",&x) && x) {
 90             BuildGraph(i, x);
 91             cas[q][1] = i, cas[q][2] = x;
 92             q++;
 93         }
 94     }
 95     cl = 0;
 96     memset(color, 0, sizeof(color));
 97     memset(vis, 0, sizeof(vis));
 98     for ( int i = 1; i <= n; ++i ) {
 99         if( !vis[i] ) {
100             tarjan(i);
101         }
102     }
103     for ( int i = 1; i < q; ++i ) {
104         if(color[cas[i][1]] != color[cas[i][2]]) {
105             out[color[cas[i][1]]]++;
106             in[color[cas[i][2]]]++;
107         }
108     }
109     int num_in = 0, num_out = 0;
110     for ( int i = 1; i <= cl; ++i ) {
111         if(in[i] == 0) {
112             num_in++;
113         }
114         if(out[i] == 0) {
115             num_out++;
116         }
117     }
118     if(cl == 1) {
119         puts("1
0");
120     }
121     else 
122         printf("%d
%d
",num_in, max(num_in, num_out));
123     return 0;
124 }

View Code