題意：就是給我們一個網絡?讓我們求

1?選擇最少的點傳信 能夠使得這個信息傳遍整個網絡

2?求加的最少的邊?使得?加上這些邊后整個圖任取一個點信息就可以傳到網絡中任何一個店

分析：?對于1問?可以用tarjan縮點?把所有的強聯通分量縮成一個點?去考慮?然后求一下出度為0的點?就是讓信息傳遍整個網絡的點的數量?如果這里選擇根據出度的數量排序用BFS把盡可能多的點標記的做法?會WA?因為用BFS去考慮的話?只考慮了出度沒有考慮入度?有些點考慮不到?就是那些入度為0出度比較小的點?網絡中只有搞定了這些點才能讓一個信息傳遍整個網絡?因為入度為0的點?無論怎么考慮出度?都不會有邊能夠溝通到這類點?

對于2問?還是統計出入度和出度為0的點?我們考慮?對于一個網絡?只要把他改造成一個強聯通圖?這個圖中的任意亮點就都可達了

也就是解決入度為0和出度為0的點?因為入度為0的點?沒人穿的到他?出度為0的點信息給他出不去?所以當我們讓這兩類點一對一互相聯通?剩下的多余的任意連?即可溝通整個網絡

import java.io.BufferedInputStream; import java.io.BufferedOutputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.PriorityQueue; import java.util.Scanner;class node implements Comparable<node>{int id,edge;node(){}node(int a,int b){this.id = a;this.edge = b;}@Overridepublic int compareTo(node p) {// TODO Auto-generated method stubif(p.edge<=this.edge)return 1;else return -1;}}public class Main {static final int maxn = 110;static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));static ArrayDeque<Integer> que = new ArrayDeque<Integer>();static ArrayDeque<Integer> S = new ArrayDeque<Integer>();static int head[] = new int[maxn*maxn];static int to[] = new int[maxn*maxn];static int next[] = new int[maxn*maxn];static boolean bok[] = new boolean[maxn];static boolean isS[] = new boolean[maxn];static int tag=0,cnt=0,ans1 =0 ,ans2=0,ind;static int dfn[] = new int[maxn];static int low[] = new int[maxn];static node nod[] = new node[maxn];static int[] id = new int[maxn];static int cir;static int in[] = new int [maxn];static int out1[] = new int[maxn];static void dfs(int x) {dfn[x] = low[x] = ++ind;S.push(x);isS[x] = true;for(int i=head[x];i!=-1;i = next[i]) {int t=to[i];if(dfn[t]==0) {dfs(t);low[x] = Math.min(low[t], low[x]);}else if(isS[t])low[x] = Math.min(low[x],dfn[t]);}if(dfn[x]==low[x]){ans2++;++cir;while(true){int t;if(!S.isEmpty()) {t = S.peek();S.pop();isS[t] = false;id[t] = cir; if(t==x)break;}}}} static void addEdge(int x,int t) { to[tag] = t;next[tag] = head[x];head[x] = tag++;}public static void main(String[] args) {Scanner sc = new Scanner(new BufferedInputStream(System.in));while(sc.hasNext()) {int n = sc.nextInt();Arrays.fill(head,-1);Arrays.fill(bok, false);Arrays.fill(isS, false);Arrays.fill(dfn, 0);Arrays.fill(low, 0);Arrays.fill(in,0);Arrays.fill(out1, 0);cir = tag=cnt=ans1=ans2=ind=0;for(int i=1;i<=n;i++) {if(nod[i]==null)nod[i] = new node(i,0);else {nod[i].id = i;nod[i].edge=0;}while(true) {int t = sc.nextInt();if(t==0)break;addEdge(i,t); } }for(int i=1;i<=n;i++) {if(dfn[i]==0) {S.clear();dfs(i);}}for(int i=1;i<=n;i++) {for(int j = head[i];j!=-1;j=next[j]){int t = to[j];if(id[t]!=id[i]){in[id[t]]++;out1[id[i]]++;}}}int Iy = 0;for(int i=1;i<=cir;i++)if(in[i]==0) {ans1++;}else if(out1[i]==0) {Iy++;}out.println(ans1);if(cir==1)out.println(0);else out.println(Math.max(ans1, Iy));out.flush(); }} }

總結

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

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