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 1 2

題意：

N個(gè)學(xué)校之間有單向的網(wǎng)絡(luò)，每個(gè)學(xué)校可以通過(guò)單向網(wǎng)絡(luò)向周邊的學(xué)校傳輸信息。

問(wèn)題1：初始至少需要向多少個(gè)學(xué)校發(fā)放信息，使得網(wǎng)絡(luò)內(nèi)所有的學(xué)校最終都能收到信息。

問(wèn)題2：至少需要添加幾條邊，使得任意向一個(gè)學(xué)校發(fā)送信息后，經(jīng)過(guò)若干次傳送，所有的學(xué)校都能收到信息。

題解：

分析題意發(fā)現(xiàn)其實(shí)就是問(wèn)對(duì)于一個(gè)有向無(wú)環(huán)圖：
1.至少要選幾個(gè)點(diǎn)，才能從這些點(diǎn)出發(fā)到達(dá)所有點(diǎn) 。

2.至少加入幾條邊，就能從圖中任何一個(gè)點(diǎn)出發(fā)到達(dá)所有點(diǎn)。

當(dāng)然圖不一定是無(wú)環(huán)圖，那么就用到了Tarjan算法來(lái)找到強(qiáng)連通分量，然后再縮點(diǎn)就變成了有向無(wú)環(huán)圖。

然后不難想出對(duì)于第一個(gè)問(wèn)題答案就是有向無(wú)環(huán)圖中入度為0的點(diǎn)的個(gè)數(shù)。對(duì)于第二個(gè)問(wèn)題仔細(xì)想一下就發(fā)現(xiàn)了如果要達(dá)到題意肯定每個(gè)點(diǎn)都有出有入，所以要消滅所有入度為零和出度為零的點(diǎn)，所以如果入度為0的個(gè)數(shù)是n，出度為0的個(gè)數(shù)是m，至少添加邊的條數(shù)就是max(n,m)。

代碼：

#include <iostream> #include <cstring> #include <cstdio> #include <cstdlib>using namespace std;#define MAXN 205bool is_instack[MAXN];//記錄節(jié)點(diǎn)是否在棧中 int stack[MAXN],top; bool map[MAXN][MAXN];//存圖，這里用的矩陣僅供理解，具體做題自己調(diào)整。 int DFN[MAXN];//記錄節(jié)點(diǎn)第一次被訪問(wèn)時(shí)的時(shí)間 int LOW[MAXN];//記錄節(jié)點(diǎn)與節(jié)點(diǎn)的子樹(shù)節(jié)點(diǎn)中最早的步數(shù) int time; int Belong[MAXN];//記錄每個(gè)節(jié)點(diǎn)屬于的強(qiáng)連通分量編號(hào) int N,cnt;//N是點(diǎn)數(shù)，cnt是強(qiáng)連通分量編號(hào)。void Tarjan(int x){DFN[x] = LOW[x] = ++time;is_instack[x] = true;stack[++top] = x;for(int i=1 ; i<=N ; ++i){if(map[x][i] == false)continue;if(!DFN[i]){Tarjan(i);if(LOW[i]<LOW[x]){LOW[x] = LOW[i];}}else if(is_instack[i] && DFN[i]<DFN[x]){ //這里注意不能直接else，因?yàn)镈FN[i]！=0還有可能是橫叉邊。LOW[x] = min(LOW[x],DFN[i]);}}if(DFN[x] == LOW[x]){++cnt;int mid;do{mid = stack[top--];is_instack[mid] = false;Belong[mid] = cnt;}while(mid != x);} }int in[MAXN];//記錄縮點(diǎn)后點(diǎn)的入度 int out[MAXN];//記錄縮點(diǎn)后點(diǎn)的出度 void init(){memset(map,false,sizeof(map));memset(DFN,0,sizeof(DFN));memset(LOW,0,sizeof(LOW));memset(in,0,sizeof(in));memset(out,0,sizeof(out));memset(is_instack,false,sizeof(is_instack));time = 0;cnt = 0;top = 0; }int main(){while(scanf("%d",&N)!=EOF){init();for(int i=1 ; i<=N ; ++i){int t;while(scanf("%d",&t) && t)map[i][t] = true;}for(int i=1 ; i<=N ; ++i){if(!DFN[i])Tarjan(i);//有可能不是連通圖所以遍歷一遍。 }for(int i=1 ; i<=N ; ++i){for(int j=1 ; j<=N ; ++j){if(map[i][j] && Belong[i] != Belong[j]){++out[Belong[i]];++in[Belong[j]];}}}if(cnt==1){printf("1\n0\n");continue;}int inzero = 0,outzero = 0;for(int i=1 ; i<=cnt ; ++i){if(!in[i])++inzero;if(!out[i])++outzero;}printf("%d\n%d\n",inzero,max(inzero,outzero));}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/vocaloid01/p/9514080.html

總結(jié)

以上是生活随笔為你收集整理的POJ - 1236 Network of Schools的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。