专栏首页数据结构与算法P2746 [USACO5.3]校园网Network of Schools

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

题目描述

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

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

输入输出格式

输入格式:

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

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

输出格式:

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

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

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

输入输出样例

输入样例#1:

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

输出样例#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 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3674: 可持久化并查集加强版

    Description Description: 自从zkysb出了可持久化并查集后…… hzwer:乱写能AC,暴力踩标程 KuribohG:我不路径压缩就...

    attack
  • BZOJ 3714: [PA2014]Kuglarz(最小生成树)

    Description 魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花...

    attack
  • P1967 货车运输

    题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想...

    attack
  • 3674: 可持久化并查集加强版

    Description Description: 自从zkysb出了可持久化并查集后…… hzwer:乱写能AC,暴力踩标程 KuribohG:我不路径压缩就...

    attack
  • P1807 最长路_NOI导刊2010提高(07)

    题目描述 设G为有n个顶点的有向无环图,G中各顶点的编号为1到n,且当为G中的一条边时有i < j。设w(i,j)为边的长度,请设计算法,计算图G中<1,n>间...

    attack
  • P3371 【模板】单源最短路径

    题目描述 如题,给出一个有向图,请输出从某一点出发到所有点的最短路径长度。 输入输出格式 输入格式: 第一行包含三个整数N、M、S,分别表示点的个数、有...

    attack
  • BZOJ 3714: [PA2014]Kuglarz(最小生成树)

    Description 魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花...

    attack
  • P1967 货车运输

    题目描述 A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双向道路。每一条道路对车辆都有重量限制,简称限重。现在有 q 辆货车在运输货物, 司机们想...

    attack
  • 教你从头写游戏服务器框架

    大概已经有差不多一年没写技术文章了,原因是今年投入了一些具体游戏项目的开发。这些新的游戏项目,比较接近独立游戏的开发方式。我觉得公司的“祖传”服务器框架技术不太...

    韩伟
  • 洛谷P2391 白雪皑皑(并查集)

    题目背景 “柴门闻犬吠,风雪夜归人”,冬天,不期而至。千里冰封,万里雪飘。空中刮起了鸭毛大雪。雪花纷纷,降落人间。 美能量星球(pty 在 spore 上的一个...

    attack

扫码关注云+社区

领取腾讯云代金券