Network of Schools
A number of schools are connected to a computer network. Agreements have been developed among those schools: each school maintains a list of schools to which it distributes software (the “receiving schools”). Note that if B is in the distribution list of school A, then A does not necessarily appear in the list of school B
You are to write a program that computes the minimal number of schools that must receive a copy of the new software in order for the software to reach all schools in the network according to the agreement (Subtask A). As a further task, we want to ensure that by sending the copy of new software to an arbitrary school, this software will reach all schools in the network. To achieve this goal we may have to extend the lists of receivers by new members. Compute the minimal number of extensions that have to be made so that whatever school we send the new software to, it will reach all other schools (Subtask B). One extension means introducing one new member into the list of receivers of one school.
Input
The first line contains an integer N: the number of schools in the network (2 <= N <= 100). The schools are identified by the first N positive integers. Each of the next N lines describes a list of receivers. The line i+1 contains the identifiers of the receivers of school i. Each list ends with a 0. An empty list contains a 0 alone in the line.
Output
Your program should write two lines to the standard output. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.
Sample Input
5
2 4 3 0
4 5 0
0
0
1 0
Sample Output
12
Source
题目类型：有向图强连通分量+缩点
算法分析：易知同一个强连通分量A中的学校之间可以相互拷贝软件，若外部一个点a和A中的点b相连，则a处的软件可以传遍A。反之若A中的点a和外部的一个点b相连，则b和A中所有的点相连，所以可以缩点。最后答案a的结果是缩点后出度为0的顶点个数。之后为了能够将缩点后的图填最少的边构建成一个强连通图，易知需要在出度为0的点和入度为0的点之间连边。直到所有出度为0的点和入度为0的点都没有为止。这样答案b的结果就是出度为0的点个数和入度为0的点个数之间的较大值。注意：当缩点后只有一个点时，需要特判输出0！！！
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 |
/************************************************* Author :supermaker Created Time :2016/1/23 14:04:32 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 166 + 66; int dfn[maxn], low[maxn], belong[maxn], indeg[maxn], outdeg[maxn]; int n, id, tot; bool instack[maxn]; vector <int> g[maxn]; stack <int> sta; void dfs (int u) { dfn[u] = low[u] = ++id; sta.push (u); instack[u] = true; for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (!dfn[v]) { dfs (v); low[u] = min (low[u], low[v]); } else if (instack[v]) low[u] = min (low[u], dfn[v]); } if (low[u] == dfn[u]) { tot++; int tt; do { tt = sta.top (); sta.pop (); instack[tt] = false; belong[tt] = tot; } while (!sta.empty () && tt != u); } } void SS () { memset (dfn, 0, sizeof (dfn)); memset (low, 0, sizeof (low)); memset (instack, false, sizeof (instack)); id = tot = 0; while (!sta.empty ()) sta.pop (); for (int i = 1; i <= n; i++) if (!dfn[i]) dfs (i); } int main() { //CFF; //CPPFF; while (scanf ("%d", &n) != EOF) { for (int i = 0; i < maxn; i++) g[i].clear (); for (int i = 1; i <= n; i++) { int u; while (scanf ("%d", &u) != EOF) { if (u == 0) break; g[i].push_back (u); } } SS (); set <PII> seta; memset (indeg, 0, sizeof (indeg)); memset (outdeg, 0, sizeof (outdeg)); for (int u = 1; u <= n; u++) for (int i = 0; i < g[u].size (); i++) { int v = g[u][i]; if (belong[u] != belong[v] && seta.find (PII (belong[u], belong[v])) == seta.end ()) { indeg[belong[v]]++; outdeg[belong[u]]++; seta.insert (PII (belong[u], belong[v])); } } int resa = 0, resb = 0; for (int i = 1; i <= tot; i++) { if (!indeg[i]) resa++; if (!outdeg[i]) resb++; } printf ("%d\n", resa); if (tot == 1) puts ("0"); else printf ("%d\n", max (resa, resb)); } return 0; } |
- « 上一篇：poj2553
- poj2318：下一篇 »