POJ1236 Network of Schools

POJ1236 Network of Schools

​​题目描述​​

输入

52 4 3 04 5 0001 0

输出

12

题意与思路:

A—>B,但B–/->A说明是个有向图.子任务A:求需要收到新软件的学校数量.也就是说只要我们给这几个发了,那么其他学校也都能收到.解决:先利用Tarjan求出连通分量,然后对其进行缩点,之后统计每个缩点的入度.入度为0,则说明必须向这个连通分量中发一个.求强连通分量缩点后入度为0的个数即为所求.

子任务B:发送到任意学校,该软件都可覆盖整个网络,说明要把这个网络构建成一个强连通图.题目是求添加扩展边的数目.解决:先利用Tarjan求出连通分量,然后对其进行缩点,之后统计每个缩点的入度,出度.对于入度为0的缩点我们需要添加个入度边(不然软件谁传进来呢?);对于出度为0的缩点,我们需要添加一个出度边(总不能传到这里就死了吧.啊呜~~~) ,题目的意思是求最少的,所以我们可以把一条边添加在入度为0和出度为0的点之间,这样添加一条边,就解决了两个缩点. 程序中我们我们需要的边数: ​​max(ans1,ans2)//ans1,ans2分别为入度,出度的缩点数量​​

最后注意一下当连通分量(缩点)为1时,子任务A只需要发送到1个学校,子任务B我们不需要添加其他边了.

图解

算法设计

参考代码

#include#include#includeusing namespace std;const int maxn = 100+10;int n,m,num,cnt,id,head[maxn],ins[maxn],low[maxn],dfn[maxn],belong[maxn],in[maxn],out[maxn];stack s;struct Edge{ int to,next;}e[maxn*maxn];void add(int u,int v){ e[++num].next = head[u]; e[num].to = v; head[u] = num;}void Tarjan(int u){ low[u] = dfn[u] = ++cnt; s.push(u); ins[u] = 1; for(int i = head[u]; i; i = e[i].next){ int v = e[i].to; if(!dfn[v]){ Tarjan(v); low[u] = min(low[u],low[v]); }else if(ins[v]){ low[u] = min(low[u],low[v]); } } if(low[u]==dfn[u]){ int v; id++; do{ v = s-(); s.pop(); ins[v] = 0; belong[v]=id;//为连通分量标号 }while(u!=v); }}void solveDegree(){//求每个连通分量的入度,出度 for(int u = 1; u <= n; u++){//遍历每条边. 求度 for(int i = head[u]; i; i = e[i].next){ int v = e[i].to; if(belong[u]!=belong[v]){//中间可能还有平行边呢.. 不过不用想那么多. out[belong[u]]++; in[belong[v]]++; } } }} int main() { int v; cin>>n;//5 for(int u = 1; u <= n; u++){ while(cin>>v&&v){ add(u,v); } } for(int i = 1; i<=n; i++){ if(!dfn[i]){ Tarjan(i); } } if(id==1){//强连通分量为1的特殊处理. cout<<1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。