usaco training 5.3.3 Network of Schools 題解

【原題】

Network of Schools

IOI '96 Day 1 Problem 3

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.

PROGRAM NAME: schlnet

INPUT FORMAT

The first line of the input file 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.

SAMPLE INPUT (file schlnet.in)

5
2 4 3 0
4 5 0
0
0
1 0
      

OUTPUT FORMAT

Your program should write two lines to the output file. The first line should contain one positive integer: the solution of subtask A. The second line should contain the solution of subtask B.

SAMPLE OUTPUT (file schlnet.out)

1
2      

【譯題】

描述

一些學校連入一個電腦網絡。那些學校已訂立了協定：每個學校都會給其它的一些學校分發軟體（稱作“接受學校”）。注意即使 B 在 A 學校的分發清單中， A 也不一定在 B 學校的清單中。

你要寫一個程式計算，根據協定，為了讓網絡中所有的學校都用上新軟體，必須接受新軟體副本的最少學校數目（子任務 A）。更進一步，我們想要确定通過給任意一個學校發送新軟體，這個軟體就會分發到網絡中的所有學校。為了完成這個任務，我們可能必須擴充接收學校清單，使其加入新成員。計算最少需要增加幾個擴充，使得不論我們給哪個學校發送新軟體，它都會到達其餘所有的學校（子任務 B）。一個擴充就是在一個學校的接收學校清單中引入一個新成員。

[編輯]格式

PROGRAM NAME: schlnet

INPUT FORMAT 輸入檔案的第一行包括一個整數 N：網絡中的學校數目（2 <= N <= 100）。學校用前 N 個正整數辨別。接下來 N 行中每行都表示一個接收學校清單（分發清單）。第 i+1 行包括學校 i 的接收學校的辨別符。每個清單用 0 結束。空清單隻用一個 0 表示。

OUTPUT FORMAT

你的程式應該在輸出檔案中輸出兩行。第一行應該包括一個正整數：子任務 A 的解。第二行應該包括子任務 B 的解。

[編輯]SAMPLE INPUT (file schlnet.in)

5
2 4 3 0
4 5 0
0
0
1 0
      

[編輯]SAMPLE OUTPUT (file schlnet.out)

1
2      

【分析】這道題就是求強連通分量以及一些拓展應用。有關強連通算法，詳見這裡。

【第一問】相當于給你一個圖，選最少的點使你能到達任何一點。解法很簡單。首先我們縮點，然後答案就是所有入度為0的點的個數。因為所有入度為0的點我們都是一定無法到達的。

【第二問】相當于給你一個圖，加上最小的邊使你在任何一點開始出發，都能到達任何一點。我們貪心的想一想。設入度為0的點有R個，出度為0的C個。

①R<=C此時最好辦了，我們把一些出度為0的點依次接在入度為0的點上，這樣一定是強連通的。

 ②如上圖情況，R>C。我們還是把出度為0的點和入度為0的點接起來。對于多出來的入度為0的點，可以重複接。

綜上所述，第二問的答案是max（R,C）

【注意】這個程式交了後一直WA。後來才發現，如果縮點後圖中隻剩一個點了（即本身是強連通的），對于第二問要特判一下，直接輸出0。

【代碼】

/*
PROG:schlnet
ID:juan1973
LANG:C++
*/
#include<stdio.h>
#include<cstring>
using namespace std;
const int v=100+5;
int num[v],map[v][v],b[v],dfs[v],low[v],f[v],cnt,cnt2;
bool flag[v],zhan[v],ff[v];
int deep,step,n,m,i,x,j,go,ans;
int get(int u){if (u==f[u]) return u;return f[u]=get(f[u]);}  
void Union(int u,int v){int uu=get(u);int vv=get(v);f[vv]=uu;}
void print(int k)                       
{
  int fa=b[deep];zhan[fa]=false;
  deep--;if (fa==k) return;
  while (1)
  {
    int i=b[deep];
    Union(fa,i);
    zhan[i]=false;
    deep--;
    if (i==k) break;
  }
}
void find(int k)                  
{
  dfs[k]=low[k]=++step;
  flag[k]=true;b[++deep]=k;zhan[k]=true;
  for (int i=1;i<=num[k];i++)
  {
    int go=map[k][i];
    if (!flag[go])
    {
      find(go);if (low[go]<low[k]) low[k]=low[go];
    }
    if ((zhan[go])&&(dfs[go]<low[k])) low[k]=dfs[go];
  }
  if (dfs[k]==low[k]) print(k);
}
void first()
{
  int i,j;
  memset(ff,0,sizeof(ff));
  for (i=1;i<=n;i++)
  {
    int fa=get(i);
    for (j=1;j<=num[i];j++)
    {
      int go=map[i][j];
      if (get(go)!=fa) ff[get(go)]=true;
    }
  }
  for (i=1;i<=n;i++) if (f[i]==i&&!ff[i]) cnt++;
  printf("%ld\n",cnt);
}
void second()
{
  int i,j;bool bre;
  memset(ff,0,sizeof(ff));
  for (i=1;i<=n;i++)
  {
    int fa=get(i);bre=false;
    for (j=1;j<=num[i];j++)
    {
      int go=map[i][j];
      if (fa!=get(go)) {bre=true;break;}
    }
    if (bre) ff[fa]=true;
  }
  for (i=1;i<=n;i++)
    if ((f[i]==i)&&(!ff[i])) cnt2++;
  ans=cnt2>cnt?cnt2:cnt;int tepan=0;
  for (i=1;i<=n;i++) if (f[i]==i) tepan++;
  if (tepan==1) ans=0;
  printf("%ld\n",ans);
}
int main()
{
  freopen("schlnet.in","r",stdin);
  freopen("schlnet.out","w",stdout);
  scanf("%ld",&n);
  for (i=1;i<=n;i++)
  {
    scanf("%ld",&x);
    while (x>0)
    {
      map[i][++num[i]]=x;
      scanf("%ld",&x);
    }
  }
  step=0;deep=1;b[1]=1;zhan[1]=true;
  for (i=1;i<=n;i++) f[i]=i;
  for (i=1;i<=n;i++)
    if (!flag[i]) find(i);
  first();
  second();
  return 0;
}