首页 > > 程序设计 > C/C++ >

P2746 [USACO5.3]校园网Network of Schools

2018-06-17 22:15:13来源：未知阅读 ()

题目描述

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

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

输入输出格式

输入格式：

输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。

接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。

输出格式：

你的程序应该在输出文件中输出两行。

第一行应该包括一个正整数：子任务 A 的解。

第二行应该包括子任务 B 的解。

输入输出样例

输入样例#1：

输出样例#1：

1
2

说明

题目翻译来自NOCOW。

USACO Training Section 5.3

第一问：至少要给多少个学校软件，才能保证所有学校都有软件用，也就是求缩点后入度为0的点的个数（因为入度为0的话没有其他学校能传软件给它）
第二问：使缩点后所有学校的入度和出度都大于0（这样就可以给任意学校软件，然后所有学校都能用上软件

如果是一个强连通图需要特判。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 #include<stack>
  8 using namespace std;
  9 const int MAXN=1000001;
 10 static void read(int &n)
 11 {
 12     char c='+';int x=0;bool flag=0;
 13     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 14     while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+(c-48);c=getchar();}
 15     flag==1?n=-x:n=x;
 16 }
 17 struct node
 18 {
 19     int u,v,nxt;
 20 }edge[MAXN];
 21 int head[MAXN];
 22 int num=1;
 23 void add_edge(int x,int y)
 24 {
 25     edge[num].u=x;
 26     edge[num].v=y;
 27     edge[num].nxt=head[x];
 28     head[x]=num++;
 29 }
 30 int dfn[MAXN];
 31 int low[MAXN];
 32 int tot=0;
 33 bool vis[MAXN];
 34 int color[MAXN];
 35 int colornum;
 36 stack<int>s;
 37 int rudu[MAXN];
 38 int chudu[MAXN];
 39 void tarjan(int now)
 40 {
 41     dfn[now]=low[now]=++tot;
 42     vis[now]=1;
 43     s.push(now);
 44     for(int i=head[now];i!=-1;i=edge[i].nxt)
 45     {
 46         if(!dfn[edge[i].v])
 47         {
 48             tarjan(edge[i].v);
 49             low[now]=min(low[now],low[edge[i].v]);
 50         }
 51         else if(vis[edge[i].v])// 公共祖先 
 52         {
 53             low[edge[i].u]=min(low[edge[i].u],dfn[edge[i].v]);
 54         }
 55     }
 56     if(dfn[now]==low[now])// root
 57     {
 58         colornum++;
 59         while(now!=s.top())
 60         {
 61             if(!color[s.top()])
 62             color[s.top()]=colornum;
 63             vis[s.top()]=0;
 64             s.pop();
 65         }
 66         if(!color[s.top()])
 67         color[s.top()]=colornum;
 68         vis[s.top()]=0;
 69         s.pop();
 70     }
 71 }
 72 int main()
 73 {
 74     //freopen("schlnet.in","r",stdin);
 75     //freopen("schlnet.out","w",stdout);
 76     int n;
 77     memset(head,-1,sizeof(head));
 78     read(n);
 79     for(int i=1;i<=n;i++)
 80     {
 81         int to;
 82         while(scanf("%d",&to)&&to!=0)
 83             add_edge(i,to);
 84     }
 85     
 86     for(int i=1;i<=n;i++)
 87         if(!dfn[i])
 88             tarjan(i);
 89     memset(vis,0,sizeof(vis));
 90     
 91     for(int i=1;i<=n;i++)
 92         for(int j=head[i];j!=-1;j=edge[j].nxt)
 93             if(color[edge[j].u]!=color[edge[j].v])
 94              {
 95                  rudu[color[edge[j].v]]++;
 96                  chudu[color[edge[j].u]]++;
 97              }
 98     int ans1=0;
 99     int ans2=0;
100     for(int i=1;i<=colornum;i++)
101     {
102         if(!rudu[i])
103             ans1++;
104         if(!chudu[i])
105             ans2++;
106     }
107     ans2=max(ans2,ans1);
108     if(colornum==1)
109     ans1=1,ans2=0;
110     printf("%d\n%d",ans1,ans2);
111     return 0;
112 }