ZOJ 2588 Burning Bridges（无向连通图求割边）-白红宇

ZOJ 2588 Burning Bridges（无向连通图求割边）

阅读量：4326 次

发布时间：2019-06-06

本文共 1074 字，大约阅读时间需要 3 分钟。

题目地址：

由于数组开小了而TLE了。。这题就是一个求无向连通图最小割边。仅仅要推断dfn[u]是否<low[v]，由于low指的当前所能回到的祖先的最小标号，增加low[v]大于dfn[u]时，说明v无法通过其它边回到u之前的点。也就是说v假设想要回到u的祖先点。必需要经过u点，那这条边非常明显就是一条割边。这题还要去重边，假如有重边的话。说明怎么销毁哪条边总能通过还有一条边，所以仅仅要有重边。说明这两点之间没有割边。

代码例如以下；

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #include 
              
               #include 
               
                using namespace std;int head[20020], cnt, index1, ans;int low[20103], dfn[20103], road[20103];struct node{ int num, u, v, next, tag;} edge[220000];void add(int num, int u, int v){ int i; for(i=head[u]; i!=-1; i=edge[i].next) { if(edge[i].v==v) break; } if(i!=-1) { edge[i].tag=1; return ; } edge[cnt].tag=0; edge[cnt].num=num; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++;}void tarjan(int u, int fa){ low[u]=dfn[u]=++index1; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].v; if(v==fa) continue ; if(!dfn[v]) { tarjan(v,u); low[u]=min(low[u],low[v]); if(dfn[u]

转载于:https://www.cnblogs.com/claireyuancy/p/6991980.html

你可能感兴趣的文章