P2746 [USACO5.3]学校网Network of Schools,p2746usaco5.3

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

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

主题材料陈诉

有的学校连入三个Computer网络。那一个高校已签定了公约:各类高校都会给其它的有些这个学校分发软件(称作“接受高校”)。注意固然B 在 A 高校的分发列表中, A 也不确定在 B 高校的列表中。

你要写叁个顺序计算,依据商业事务,为了让网络中有着的母校都用上新软件,必需接受新软件别本的最少学校多少(子职责A)。更进一竿,我们想要鲜明通过给自由三个这个学院发送新软件,这么些软件就能够散发到网络中的全数学校。为了产生那个职分,我们也许必得增添接收高校列表,使其踏入新成员。计算最少须求追加多少个扩充,使得不论我们给哪些高校发送新软件,它都会达到别的具有的院所(子任务B)。二个增加正是在多个高校的选取高校列表中引进多少个新成员。

难点汇报

有的学府连入一个计算机互联网。那多少个高校已立下了合同:种种学校都会给任何的片段高校分发软件(称作“接受高校”)。注意纵然B 在 A 高校的分发列表中, A 也不自然在 B 学校的列表中。

您要写三个主次总括,依据合同,为了让互联网中全数的这个学院都用上新软件,必得承受新软件别本的最少学校数量(子任务A)。更上一层楼,大家想要分明通过给自由二个学院发送新软件,那几个软件就能散发到互连网中的全体高校。为了成功这么些职责,我们或者必需扩张接收高校列表,使其步入新成员。总结最少供给扩张几个扩充,使得不论我们给哪个高校发送新软件,它都会达到任何具备的院所(子义务B)。一个增加正是在三个学校的接受高校列表中引进三个新成员。

输入输出格式

输入格式:

 

输入文件的首先行包涵一个整数 N:互连网中的高校多少(2 <= N <=
100)。学校用前 N 个正整数标记。

接下去 N 行中每行都意味壹个吸取高校列表(分发列表)。第 i+1 行包罗这个学校 i
的采用学校的标记符。各样列表用 0 甘休。空驶列车表只用一个 0 表示。

 

出口格式:

 

您的次第应该在输出文件中输出两行。

第一行应有满含一个正整数:子任务 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

输入输出样例

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

 

http://www.bkjia.com/cjjc/1218358.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1218358.htmlTechArticleP2746 [USACO5.3]学校网Network of
Schools,p2746usaco5.3 标题叙述一些本校连入四个Computer互联网。那多少个高校已立下了和睦:各个学校都会给任何的一些学…

说明

主题材料翻译来自NOCOW。

USACO Training Section 5.3

分析

1.求最少让多少人领会就可以形成让具有的人都驾驭音信,最少知道的人的数目即为缩完点后入度为零的点的个数

2.最少加入几条边就足以使二个树产生三个强连通图,加的边的条数即为缩完点后
马克斯(入度为零的点的个数,出度为零的点的个数)

定理:自便一棵有向图的树,成为强联通分量,则必要扩充的边数为max(入度为0的点的个数,出度为0的点的个数)

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<cstdlib>
 6 
 7 using namespace std;
 8 
 9 const int N = 210;
10 const int M = 50010;
11 struct Edge{
12     int to,nxt;
13 }e[M];
14 int head[N],dfn[N],low[N],st[N],bel[N];
15 int ru[N],chu[N];
16 bool vis[N];
17 int tn,tot,top,tot2,cnt;
18 
19 inline char nc() {
20     static char buf[100000],*p1 = buf,*p2 = buf;
21     return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2) ? 
22 
23 EOF : *p1++;
24 }
25 inline int read() {
26     int x = 0,f = 1;char ch = nc();
27     for (; ch<'0'||ch>'9'; ch = nc()) 
28         if (ch=='-') f = -1;
29     for (; ch>='0'&&ch<='9'; ch = nc()) 
30         x = x*10+ch-'0';
31     return x * f;
32 }
33 
34 void add_edge(int u,int v) {
35     e[++tot].to = v,e[tot].nxt = head[u],head[u] = tot;
36 }
37 
38 void tarjan(int u) {
39     dfn[u] = low[u] = ++tn;
40     st[++top] = u;
41     vis[u] = true;
42     for (int i=head[u]; i; i=e[i].nxt) {
43         int v = e[i].to;
44         if (!dfn[v]) {
45             tarjan(v);
46             low[u] = min(low[u],low[v]);
47         }
48         else if (vis[v]) 
49             low[u] = min(low[u],dfn[v]);
50     }
51     if (dfn[u] == low[u]) {
52         ++cnt;
53         do {
54             vis[st[top]] = false;
55             bel[st[top]] = cnt;
56             top--;
57         } while (st[top+1]!=u);
58     }
59 }
60 int main() {
61     int n = read();
62     for (int i=1; i<=n; ++i) {
63         int x = read();
64         while (x!=0) {
65             add_edge(i,x);
66             x = read();
67         }
68     }
69     for (int i=1; i<=n; ++i) 
70         if (!dfn[i]) tarjan(i);
71     for (int u=1; u<=n; ++u) {
72         for (int i=head[u]; i; i=e[i].nxt) {
73             int v = e[i].to;
74             if (bel[u] != bel[v]) {
75                 ru[bel[v]]++,chu[bel[u]]++;
76             }
77         }
78     }
79     int r = 0,c = 0;
80     for (int i=1; i<=cnt; ++i) {
81         if (ru[i]==0) r++;
82         if (chu[i]==0) c++;
83     }
84     int ans1 = r,ans2;
85     if (cnt==1) ans2 = 0;
86     else ans2 = max(r,c);
87     printf("%d\n%d",ans1,ans2);
88     return 0;
89 }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图