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)

52 4 3 04 5 0001 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)

12

 ——————————————————————题解

讲真，这道题过的真是一把辛酸泪

先说说我自己的非完美算法

强连通缩点然后所有点按照入度排序之后floodfill求出subtaskA

对于subtaskB我们对于每一个求好的连通块可以用串一串的方法来让它们强连通，对于每一个连通块中出度为0的点，可以把它们连在一起变成一个出度为0的点（需要出度为0的点的个数-1的花费）

至此，我们可以说一个连通块是“有方向的边”，它的起点是扩展时最初的点，终点是唯一出度为0的点，然后按照方向将它们连起来需要cnt（联通块个数）的花费

当然，有些时候两个连通块有共用出度为0的点，我们发现我们只关心他们的总花费，初始化总花费为所有出度为0的点总和，如果一个连通块拥有一个出度为0的点，那么我们的花费就减一

按照以上的计算答案是3

但是有反例，对于这样一个图，我们计算的答案是4（正确答案是5）

对于这个解决办法，我们可以做二分图匹配，求出最大匹配数……

所以这个办法完全起来应该是强连通缩点+floodfill+二分图匹配

但是前两步我的代码已经近160行……于是第三步我怂了……结果交上去过了……还是感谢USACO没有卡我

1 /*  2 ID: ivorysi  3 LANG: C++  4 PROG: schlnet  5 */  6 #include 
     
        7 #include 
      
         8 #include 
       
          9 #include 
        
          10 #include 
         
           11 #include 
          
            12 #include 
           
             13 #include 
            
              14 #include 
             
               15 #include 
              
                16 #define siji(i,x,y) for(int i=(x);i<=(y);++i) 17 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j) 18 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i) 19 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j) 20 #define inf 0x3f3f3f3f 21 #define ivorysi 22 #define mo 97797977 23 #define hash 974711 24 #define base 47 25 #define pss pair
               
                 26 #define MAXN 5000 27 #define fi first 28 #define se second 29 #define pii pair
                
                  30 #define esp 1e-8 31 typedef long long ll; 32 using namespace std; 33 struct node { 34 int to,next; 35 }edge[20005],edge1[20005]; 36 int head[105],sumedge,n; 37 int head1[105],sumedge1; 38 int ind[105],chd[105],col[105],cnt,tmp[105],ans; 39 int dfn[105],low[105],cur,cor,instack[105],id[105]; 40 stack
                 
                   s; 41 void add(int u,int v) { 42 edge[++sumedge].to=v; 43 edge[sumedge].next=head[u]; 44 head[u]=sumedge; 45 } 46 void add1(int u,int v) { 47 edge1[++sumedge1].to=v; 48 edge1[sumedge1].next=head1[u]; 49 head1[u]=sumedge1; 50 } 51 void init() { 52 scanf("%d",&n); 53 int a; 54 siji(i,1,n) { 55 while(scanf("%d",&a)!=EOF && a!=0) add(i,a); 56 } 57 } 58 bool cmp(const int &a,const int &b) { 59 return ind[a]
                  
                   =t) ans=0;140 else ans=t-m;141 if(cnt!=1) ans+=cnt;142 else if(cor==1) ans=0; 143 else ans=t;144 printf("%d\n",ans);145 }146 int main(int argc, char const *argv[])147 {148 #ifdef ivorysi149 freopen("schlnet.in","r",stdin);150 freopen("schlnet.out","w",stdout);151 #else152 freopen("f1.in","r",stdin);153 #endif154 extend();155 return 0;156 }
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

 

那啥，以上这些不看也罢

讲一下USACO的正解

人家根本就没用tarjan，但是思路和缩点后再做差不多。

如果缩点后再做

subtaskA 就是缩点后入度为0的点的个数

subtaskB 就是入度为0的点的个数和出度为0的点的个数取最大值（至于为什么要接着看完USACO的题解解释）

如果没有缩点 【以下来自USACO 5.3  Network of Schools Analysis --- Adam D'Angelo】

The first subtask is to find a minimal set of schools such that there is a path to every school from some school in this set. We will call this set the "tops." We can find the tops with the following algorithm:

第一个子任务是去找到一个最小的学校集合至少有一条路径是从这个集合中的学校去到每一个学校，我们可以叫这个集合“顶端”，我们可以找到顶端用如下的算法

1. Mark each school as not being a top and not having a top. Having a top means that a school is reachable from some school which is a top.
2. Sequentially make each school N which has no top into a top. When we do this, mark off all schools reachable from it as having tops. We also mark them off as not being tops, because this is unnecessary - all schools that were being served by them can now just be served by N.

This gets us a solution to subtask A.

1. 标记每个学校为不为顶端和没有顶端，有顶端意味着从这个顶端可以到达这个学校

2.线性地使没有顶端的端点N变成顶端。当我们做这件事的时候，划分这个点能到达的所有学校为有顶端，我们也划分它们为不为顶端，因为这（把当前搜索到的点依旧当做顶端）是不必要的-他们发送文件的所有学校都可以被N当顶端时发送到。

这样我们就得到了子任务A的结果。

The second subtask is more tricky. First look at the minimal set of schools such that at least one of them can be reached from any school. This can be found by reversing all connections in the graph and finding the tops - we will call these the "bottoms."

第二个子任务更为复杂。首先看这样一个最小的学校集合，所有学校可以到达他们中的至少一个点。他们可以在图翻转后用寻找顶端的算法找到，我们叫他们“底端”。

If there is only one bottom and one top, we need only to add one connection from the bottom to the top to solve the problem: every school can get to the bottom, the bottom can get to the top, and the top can get to every school.

如果只有一个底端和一个顶端，我们只需要加一条从这个底端到这个顶端的边解决这个问题：任何学校都可以到底端，底端可以到顶端，顶端可以到任何学校

If there is more than one bottom and one top, we need to add one connection for each bottom to the top. If there is one bottom and more than one top, we need one connection from the bottom to each top.

如果有超过一个底端和一个顶端，我们需要在每一个底端和顶端之间加边，如果这有一个底端和超过一个的顶端，我们需要在这个底端到每一个顶端加一条边

The hard part is when there is more than one bottom and more than one top. In this case, there is always some bottom B and some top T such that some other top OT leads to B and T leads to some other bottom OB. Connecting B to T makes T no longer a top (because OT can do its work) and B no longer a bottom (because OB can do its work.) If we sequentially remove tops and bottoms in this manner, we get to one of the above cases. Thus, the answer is max(tops, bottoms).

最难的部分是有超过一个底端和超过一个顶端，在这种情况下，总会有这样一个底端B有一个顶端集合OT指向B ，和这样一个顶端T指向一个底端集合OB，如果连上一条从B到T的边，就会使得T不再是顶端（因为OT中的点会做T的工作），B不再是底端（因为OB中的点会做B的工作）。如果我们线性地用这种方法去除顶端和底端，我们就会得到上面三种情况的一种，因此，答案就是（顶端的个数，底端的个数）取最大值

We have to watch out for the special case of the graph already being fully connected. This leads to a tops/bottoms value of 1, but no new connections need to be made. This is done with a flood fill. 

我们需要检查这个图是不是已经强连通了，这导致tops和bottoms的值都是1，但是没有新的边需要添加。这可以用一个填充算法（也叫洪水填充）完成。

代码我就不粘了……不敢盗版权……

大家看着上面就知道怎么写了，写过了点一下Analysis去看优美无比的标算

 【悄悄粘一发tarjan缩点的算法】

1 /*  2 ID: ivorysi  3 LANG: C++  4 PROG: schlnet  5 */  6 #include 
     
        7 #include 
      
         8 #include 
       
          9 #include 
        
          10 #include 
         
           11 #include 
          
            12 #include 
           
             13 #include 
            
              14 #include 
             
               15 #include 
              
                16 #define siji(i,x,y) for(int i=(x);i<=(y);++i) 17 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j) 18 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i) 19 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j) 20 #define inf 0x3f3f3f3f 21 #define ivorysi 22 #define mo 97797977 23 #define hash 974711 24 #define base 47 25 #define pss pair
               
                 26 #define MAXN 5000 27 #define fi first 28 #define se second 29 #define pii pair
                
                  30 #define esp 1e-8 31 typedef long long ll; 32 using namespace std; 33 struct node { 34 int to,next; 35 }edge[20005],edge1[20005]; 36 int head[105],sumedge,n; 37 int head1[105],sumedge1; 38 int ind[105],chd[105],ans,a1,a2; 39 int dfn[105],low[105],cur,cor,instack[105],id[105]; 40 stack
                 
                   s; 41 void add(int u,int v) { 42 edge[++sumedge].to=v; 43 edge[sumedge].next=head[u]; 44 head[u]=sumedge; 45 } 46 void add1(int u,int v) { 47 edge1[++sumedge1].to=v; 48 edge1[sumedge1].next=head1[u]; 49 head1[u]=sumedge1; 50 } 51 void init() { 52 scanf("%d",&n); 53 int a; 54 siji(i,1,n) { 55 while(scanf("%d",&a)!=EOF && a!=0) add(i,a); 56 } 57 } 58 void tarjan(int u) { 59 dfn[u]=++cur; 60 low[u]=dfn[u]; 61 s.push(u); 62 instack[u]=1;//如果是另一个块中的点去访问不能访问之前的点 63 for(int i=head[u];i;i=edge[i].next) { 64 int v=edge[i].to; 65 if(!instack[v]) { 66 tarjan(v); 67 low[u]=min(low[v],low[u]); 68 } 69 else { 70 if(instack[v]==1) low[u]=min(low[u],dfn[v]); 71 } 72 } 73 if(dfn[u]==low[u]) { 74 ++cor; 75 while(s.top()!=u) { 76 instack[s.top()]=2; 77 id[s.top()]=cor; 78 s.pop(); 79 } 80 instack[s.top()]=2; 81 id[s.top()]=cor; 82 s.pop(); 83 } 84 } 85 86 void solve() { 87 init(); 88 siji(i,1,n) { 89 if(instack[i]==0) { 90 tarjan(i); 91 } 92 } 93 siji(i,1,n) { 94 for(int j=head[i];j;j=edge[j].next) { 95 if(id[i]!=id[edge[j].to]) { 96 add1(id[i],id[edge[j].to]); 97 } 98 } 99 }100 siji(i,1,cor) {101 for(int j=head1[i];j;j=edge1[j].next) {102 ++ind[edge1[j].to];103 ++chd[i];104 }105 }106 siji(i,1,cor) {107 if(ind[i]==0) ++a1;108 if(chd[i]==0) ++a2;109 }110 printf("%d\n",a1);111 if(cor==1) ans=0;112 else ans=max(a1,a2);113 printf("%d\n",ans);114 }115 int main(int argc, char const *argv[])116 {117 #ifdef ivorysi118 freopen("schlnet.in","r",stdin);119 freopen("schlnet.out","w",stdout);120 #else121 freopen("f1.in","r",stdin);122 #endif123 solve();124 return 0;125 }