题目链接:http://poj.org/problem?id=1236

题目大意:

给你一个网络(有向图),有两个任务:
①求出至少同时需要几份副本可以使得整个网络都获得副本
②至少添加多少信息表(有向边)使得副本传到任一点,都可以使得整个网络都获得副本

解题思路:

即给定一个有向图,求:

①至少要选几个顶点,才能做到从这些顶点出发,可以到达全部顶点

②至少要加多少条边,才能使得从任何一个顶点出发,都能到达全部顶点
缩点后,分别求出出度入度为0的点数为sum1,sum2,
问题①的答案就为sum2;
问题②的答案为max(sum1,sum2)(即使得所有点的出度入度都大于0)。
注意,只有一个点时,不需要添加边,答案为1,0。

代码

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
using namespace std;
const int N=; int n,cnt,num; //cnt为当前dfs序,num为缩点编号
int low[N],dfn[N],fa[N],indeg[N],outdeg[N];//dfn为dfs序,low为节点能够通过返回的最早的祖先(注意这里跟求割边割点里的low不同)
vector<int>v[N]; //fa为节点所属的强联通分量的编号.indeg和outdeg为缩点的入度、出度
stack<int>sk; void init(){
cnt=num=;
for(int i=;i<=n;i++){
v[i].clear();
}
memset(fa,,sizeof(fa));
memset(low,,sizeof(low));
memset(dfn,,sizeof(dfn));
memset(indeg,,sizeof(indeg));
memset(outdeg,,sizeof(outdeg));
} //求强联通分量
void tarjan(int u){
low[u]=dfn[u]=++cnt;
sk.push(u);
for(int i=;i<v[u].size();i++){
int t=v[u][i];
if(!dfn[t]){ //未被访问
tarjan(t);
low[u]=min(low[u],low[t]);
}
else if(!fa[t]) low[u]=min(low[u],dfn[t]); //被访问过且在栈中
}
if(low[u]==dfn[u]){
num++;
while(!sk.empty()){
int t=sk.top();
sk.pop();
fa[t]=num;
if(t==u) break;
}
}
} int main(){
while(~scanf("%d",&n)){
init();
for(int i=;i<=n;i++){
int x;
while(~scanf("%d",&x)&&x) v[i].push_back(x);
}
for(int i=;i<=n;i++){ //遍历所有点
if(!dfn[i]) tarjan(i);
}
for(int i=;i<=n;i++){ //缩点,并求出相应的出度入度是否为0(注意不是求出入度)
for(int j=;j<v[i].size();j++){
int t=v[i][j];
if(fa[t]!=fa[i]){
outdeg[fa[i]]=;
indeg[fa[t]]=;
}
}
}
int sum1=,sum2=;
for(int i=;i<=num;i++){
if(outdeg[i]==)
sum1++;
if(indeg[i]==)
sum2++;
}
if(num==) //只有一个点时要特判
puts("1\n0");
else printf("%d\n%d\n",sum2,max(sum1,sum2));
}
return ;
}

最新文章

  1. Git 的深入理解与GitHub托管服务(转)
  2. 搭建Maven私服
  3. AngularJS html+DOM+ng-click事件
  4. 【iOS】UIKit框架 学习笔记
  5. 如何下载Spring
  6. I/O复用:异步聊天
  7. sqlservice 查询该字段的值是否为数字、不包含a-z字母、获取中文的首字母
  8. [GeekBand] STL与泛型编程(3)
  9. cocos2dx Menu
  10. php 中利用json_encode和json_decode传递包括特殊字符的数据
  11. Wireshark安装、简单使用、过滤器简介
  12. Linux中dos2unix批量转换
  13. 【可持久化线段树】POJ2104 查询区间第k小值
  14. 如何配置VS使得可以通过域名或IP访问
  15. js03-javascript对象
  16. Cordova开发App使用USB进行真机调试
  17. pxe+kickstart自动化批量安装系统详解-技术流ken
  18. Ansible 拷贝文件或目录
  19. BZOJ.3227.[SDOI2008]红黑树tree(树形DP 思路)
  20. R - Dividing 多重背包

热门文章

  1. Chapter 6(树)
  2. 在ubuntu下安装opencv
  3. Service Fabric Failover Manager
  4. python基础之while语句continue以及break --语法以及案例
  5. Ansible lineinfile模块详解
  6. java8 新特性 Stream
  7. PHP7 学习笔记(一)Ubuntu 16.04 编译安装Nginx-1.10.3、 PHP7.0.9、Redis3.0 扩展、Phalcon3.1 扩展、Swoole1.9.8 扩展、ssh2扩展(全程编译安装)
  8. 通过xshell/securecrt连接linux上传/下载文件
  9. redis 批量删除keys
  10. 《设计模式》-原则六:迪米特法则(LoD)