博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
POJ 1236 Network of Schools【强连通分量+缩点】
阅读量:6260 次
发布时间:2019-06-22

本文共 877 字,大约阅读时间需要 2 分钟。

题意: 知道了N 个学校,以及每个学校提供软件支持的学校编号,一个学校得到软件支持之后便可以支持他能支持的学校,问至少对多少学校提供软件支持可以使得

          所有学校都得到软件支持,和至少在这些学校添加多少条边能使得任何一个学校得到软件支持后,其他所有学校都能得到软件支持。

分析: 先求出所有的强连通分量并进行染色缩点,找出入度为 0 的强连通分量,其个数即为使所有学校得到支持所需要提供软件支持的最小数量,  而根节点与叶子节点

          数量中的最大值即为最少添加的边数。

#include
#include
#define clr(x)memset(x,0,sizeof(x))struct node{ int to,next;}e[20000];int tot;int head[102];void add(int s,int u){ e[tot].to=u; e[tot].next=head[s]; head[s]=tot++;}int ti,sn,top;int col[102];int dfn[102],low[102],stack[102];bool ins[102];void tarjan(int u){ dfn[u]=low[u]=++ti; stack[++top]=u; ins[u]=true; int i,k; for(i=head[u];i;i=e[i].next) { k=e[i].to; if(dfn[k]==0) { tarjan(k); if(low[k]
out?in:out); } return 0;}

 

转载于:https://www.cnblogs.com/dream-wind/archive/2012/08/15/2640914.html

你可能感兴趣的文章
Appium简介及工作原理
查看>>
更换笔记本内存:自己动手修电脑(一)
查看>>
区分扫描枪输入和键盘输入的实现
查看>>
【mongdb主从复制和同步】
查看>>
下载文件downloadFile
查看>>
cf-Round542-Div2-B(贪心)
查看>>
日志挖掘(logminer)
查看>>
LaTeX技巧005:定制自己炫酷的章节样式实例
查看>>
1_NAT模式和桥接模式下的网络配置
查看>>
EF架构~为EF DbContext生成的实体添加注释(T5模板应用)
查看>>
【转】VLAN原理详解
查看>>
python --- json模块和pickle模块详解
查看>>
idea中artifacts、facets、modules是什么意思?
查看>>
FUCKED-BUG之临时对象的生死
查看>>
SP2 PRIME1 - Prime Generator
查看>>
创建和编辑 crontab 文件
查看>>
钉钉发消息
查看>>
20172309_《程序设计与数据结构(下)》_课堂测试修改报告。
查看>>
(二十九)方法调用之解析
查看>>
Springboot文件上传与下载
查看>>