cogs 908 校园网

提交地址：http://cojs.tk/cogs/problem/problem.php?pid=908

★★ 输入文件：schlnet.in 输出文件：schlnet.out 简单对比
时间限制：1 s 内存限制：128 MB

USACO/schlnet(译 by Felicia Crazy)

描述

一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意如果 B 在 A 学校的分发列表中，那么 A 不必也在 B 学校的列表中。

你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

PROGRAM NAME: schlnet

INPUT FORMAT (file schlnet.in)

输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。

OUTPUT FORMAT(file schlnet.out)

你的程序应该在输出文件中输出两行。第一行应该包括一个正整数：子任务 A 的解。第二行应该包括子任务 B 的解。

SAMPLE INPUT (file schlnet.in)

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

SAMPLE OUTPUT (file schlnet.out)

注意：凡是涉及tarjan算法缩点的，图中缩点后只有一个点的情况必须特判。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<iostream>
  4 #include<stack>
  5 
  6 #define N 110
  7 
  8 using namespace std;
  9 
 10 int n,dfn[N],low[N],top=0;
 11 int indu[N],outdu[N],ust=0,ptot[N];
 12 int father[N],t=0,head[N];
 13 bool visited[N],instack[N];
 14 stack<int> sta;
 15 struct eage
 16   {
 17       int u;
 18       int v;
 19       int last;
 20   }edge[N*N];
 21   
 22 void add_eage(int,int);
 23 void input();
 24 void tarjan(int);
 25 void count();
 26 
 27 int main()
 28   {
 29       freopen("schlnet.in","r",stdin);
 30     freopen("schlnet.out","w",stdout);
 31     input();
 32     for(int i=1;i<=n;i++)
 33       if(visited[i]==0)
 34         tarjan(i);
 35     count();
 36     fclose(stdin);fclose(stdout);
 37     return 0;
 38   }
 39 
 40 void add_edge(int u,int v)       //边表储存 
 41   {
 42       ++t;
 43       edge[t].u=u;                 //边的起点 
 44       edge[t].v=v;                 //边的终点 
 45       edge[t].last=head[u];        //从u点出发的上一条边的编号 
 46       head[u]=t;                   //t现在为从u点出发的最后一条边的编号 
 47   }
 48 
 49 void input()
 50   {
 51       scanf("%d",&n);
 52       for(int i=1;i<=n;i++)
 53       {
 54           int x;
 55           while(1)
 56             {
 57                 scanf("%d",&x);
 58                 if(x==0) break;
 59               add_edge(i,x);
 60             }
 61       }
 62     for(int i=1;i<=n;i++)        //缩点的时候要用到并查集，先初始化一下 
 63       father[i]=i;
 64   }
 65   
 66 void tarjan(int k)
 67   {
 68       visited[k]=true;
 69       dfn[k]=low[k]=top++;
 70       sta.push(k);
 71     instack[k]=true;
 72     for(int l=head[k];l;l=edge[l].last)
 73       {
 74           if(visited[edge[l].v]==0)
 75             {
 76                 tarjan(edge[l].v);
 77                 low[k]=min(low[k],low[edge[l].v]);
 78             }
 79         else
 80           if(instack[edge[l].v]==true)
 81             low[k]=min(low[k],dfn[edge[l].v]);
 82        } 
 83     if(dfn[k]==low[k])
 84       {
 85           int pp;
 86           ++ptot[0];                      //加入强连通分量的代表点 
 87           ptot[ptot[0]]=k;
 88           pp=sta.top();
 89           sta.pop();
 90           while(1)
 91             {
 92                 father[pp]=k;                //并查集缩点 
 93                 instack[pp]=false;           //把自己出栈 
 94                 if(pp==k) break;
 95                 pp=sta.top();
 96                 sta.pop();
 97             }
 98       }
 99   }
100 
101 void count()
102   {
103       for(int i=1;i<=t;i++)                   //遍历所有边，把剩下的边给相应的剩下的点 
104         {
105             int u=edge[i].u,v=edge[i].v;
106             if(father[u]!=father[v])
107               {
108                   outdu[father[u]]++;
109                   indu[father[v]]++;
110               }
111         }
112     int in=0,out=0;
113     for(int i=1;i<=ptot[0];i++)
114       {                                       //便利点，统计入度、出度为0的点的个数 
115           if(indu[ptot[i]]==0)
116             in++;
117           if(outdu[ptot[i]]==0)
118             out++;
119       }
120     if(ptot[0]==1)                     //特判只有一个强连通分量时的情况 
121       printf("1
0");
122     else
123       printf("%d
%d",in,max(in,out));
124   }

View Code