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 的解.
第一步显然要缩点...
第二步统计新点每个点的入度和初度.
第一问显然就是有多少点入度为 0, 把机子放到那些点就行了. 第二问我们把入度和初度为 0 的点连起来造环, 取数量大的那个.
值得一提的是, 缩完了以后是单点的情况要额外讨论喵
- code:
- #include <cstdio>
- int min(int x,int y){return x<y?x:y;}
- int max(int x,int y){return x>y?x:y;}
- const int N=101;
- int n;
- struct Edge
- {
- int to,next;
- }edge[N*N];
- int head[N],cnt=0;
- void add(int u,int v)
- {
- edge[++cnt].next=head[u];edge[cnt].to=v;head[u]=cnt;
- }
- int low[N],dfn[N],is[N],in[N],out[N],s[N],ha[N],tot=0,time=0,n0=0;
- void push(int x){s[++tot]=x;}
- void pop(){tot--;}
- void tarjan(int now)
- {
- low[now]=dfn[now]=++time;
- is[now]=1;
- push(now);
- for(int i=head[now];i;i=edge[i].next)
- {
- int v=edge[i].to;
- if(!dfn[v])
- {
- tarjan(v);
- low[now]=min(low[now],low[v]);
- }
- else if(is[v])
- low[now]=min(low[now],dfn[v]);
- }
- if(low[now]==dfn[now])
- {
- n0++;int k;
- do
- {
- k=s[tot];
- pop();
- is[k]=0;
- ha[k]=n0;
- }while(k!=now);
- }
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- {
- int v;
- scanf("%d",&v);
- while(v)
- {
- add(i,v);
- scanf("%d",&v);
- }
- }
- for(int i=1;i<=n;i++)
- if(!dfn[i])
- tarjan(i);
- for(int i=1;i<=n;i++)
- for(int j=head[i];j;j=edge[j].next)
- {
- int v=edge[j].to;
- if(ha[v]!=ha[i])
- in[ha[v]]++,out[ha[i]]++;
- }
- int ans1=0,ans2=0;
- if(n0==1) {printf("1\n0\n");return 0;}
- for(int i=1;i<=n0;i++)
- {
- if(!in[i]) ans1++;
- if(!out[i]) ans2++;
- }
- printf("%d\n%d\n",ans1,max(ans2,ans1));
- return 0;
- }
- 2018.6.10
来源: http://www.bubuko.com/infodetail-2638346.html