POJ1236 Network of Schools

文章目錄

• • Description
  • 題意：
  • 題解：
  • 代碼：

Description

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

題意：

給你一些點的連接關系（有向邊），具有傳遞性
然后有兩個任務
任務A：
至少要選擇多少個點，通過邊進行傳遞，可以經過所有邊
任務B：
要使所有點都可以彼此到達，最少要添加多少有向邊

題解：

并查集應該可以做吧（但我并沒有用）
我們用tarjan來做
我們先來分析和整合題意：
一個強連通分塊里面是可以相互到達的，我們可以當做一個點來處理
任務A：
我們可以進行tarjan縮點，如果一個點入度為0，也就是沒有其他點指向他，我們就必須選擇他，否則這樣的點就不會被遍歷，那么這個點就是滿足要求的
任務B：
其實就是問最少添加幾個邊可以使得整個圖變成強連通圖，
如果一個圖是強連通圖，里面所有點可以互達，就說明每個點入度出度均大于0.
那么縮點后，我們就統計入度為0的A類點數與出度為0的B類點數，只要從B類點生成一條指向A類點的有向線段即可，所以求這兩類點的較大值
總結就是：
Tarjan+強連通分量+縮點
代碼有詳細講解

代碼：

#include<iostream> #include<cstdio> #include<string> #include<cstdio> using namespace std; int n,head[10005],cnt=0,col=0,sum; int top=1,stack[10005],color[10005],dfn[10005],low[10005],vis[10005];//color記錄染色后點的顏色。 int in[10005],out[10005];//in和out分別是入度和出度。 struct net {int to,next; }e[1000000]; void add(int x,int y) {cnt++;e[cnt].to=y;e[cnt].next=head[x];head[x]=cnt; } void tarjian(int x) {sum++;dfn[x]=low[x]=sum;stack[top]=x;top++;vis[x]=1;for(int w=head[x];w!=0;w=e[w].next){if(vis[e[w].to]==0){tarjian(e[w].to);low[x]=min(low[x],low[e[w].to]);}else if(vis[e[w].to]==1)low[x]=min(low[x],dfn[e[w].to]);}if(dfn[x]==low[x]){col++;do{top--;color[stack[top]]=col;vis[stack[top]]=-1;}while(stack[top]!=x);}//常規的tarjan縮點 模板 return ; } int hym[1000000][3]; int main() {int i,k=0;cin>>n;for(i=1;i<=n;i++){int x;cin>>x;while(x!=0){k++;add(i,x);hym[k][1]=i;//1表示這條邊的始點，2表示這條邊的終點 hym[k][2]=x;//記下邊，方便之后統計入度和出度。scanf("%d",&x);}}for(i=1;i<=n;i++)if(!vis[i]) tarjian(i);for(i=1;i<=k;i++)if(color[hym[i][1]]!=color[hym[i][2]])//如果相等說明這個點在同一個強連通分量里，否則就是兩個強連通分量之間的邊//那我們分別計這個邊兩端的入度和出度 {out[color[hym[i][1]]]++;//始點記出度 in[color[hym[i][2]]]++;//終點記入度 }//同種顏色不需要統計，不同顏色更改出度和入度。int ans1=0,ans2=0;for(i=1;i<=col;i++){//cout<<in[i]<<' '<<out[i]<<endl;if(in[i]==0) ans1++;if(out[i]==0) ans2++;//尋找出度和入度為0的點數 }if(col==1) cout<<1<<endl<<0;elsecout<<ans1<<endl<<max(ans1,ans2); return 0; }

總結

以上是生活随笔為你收集整理的POJ1236 Network of Schools的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。