LA5135图论+ 割点性质运用-白红宇

LA5135图论+ 割点性质运用

阅读量：4597 次

发布时间：2019-06-09

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

1 /*  2 LA5135图论  3 割点性质运用  4   5 关键：割顶出设置逃生点是不划算的。  6 这道题的思路算是比较简单，没有推导证明的成分，是BCC性质的运用  7 注意，当整张图是BCC时，至少要设置两个逃生点，这个也算是考点，开始没想到，下次注意  8 */  9 #include 
     
       10 #include 
      
        11 #include 
       
         12 #include 
        
          13 #include 
         
           14 #include 
          
            15 #include 
           
             16 #include 
            
              17 #include 
             
               18 #include 
              
                19 #include 
               
                 20 #include 
                 21 #include 
                 
                   22 #include 
                  
                    23 #include 
                   
                     24 #define rec(i,n) for(int i=1;i<=n;i++) 25 #define INF 0x3f3f3f3f 26 using namespace std; 27 28 const int maxn = 101000 ; 29 struct edge 30 { 31 int u,v,cap,pre;//cap表示花费 32 edge(int u=0,int v=0):u(u),v(v){} 33 }Edge[maxn];//注意开两倍的边 34 int head[maxn],next[maxn],nedge;//表示读入的边的个数 35 void addedge(int u,int v) 36 { 37 Edge[++nedge]=edge(u,v);//边从1开始编号 38 next[nedge]=head[u]; 39 head[u]=nedge; 40 } 41 void edgeinit()//添边之前要初始化 42 { 43 nedge=0; 44 memset(head,-1,sizeof(head)); 45 } 46 int pre[maxn],iscut[maxn],bccno[maxn],dfs_clock,bcc_cnt; 47 vector
                    
                      bcc[maxn]; 48 stack
                     
                      S ; 49 50 int dfs(int u,int fa) 51 { 52 int lowu=pre[u]=++dfs_clock; 53 int child=0; 54 for(int i=head[u];i!=-1;i=next[i]) 55 { 56 int v=Edge[i].v; 57 edge e=(edge){u,v}; 58 if (!pre[v]) 59 { 60 S.push(e); 61 child++; 62 int lowv=dfs(v,u);//这时，u是父节点 63 lowu=min(lowu,lowv); 64 if (lowv>=pre[u]) 65 { 66 iscut[u]=true; 67 bcc_cnt++;bcc[bcc_cnt].clear(); 68 for(;;) 69 { 70 edge x=S.top();S.pop(); 71 if(bccno[x.u]!=bcc_cnt){bcc[bcc_cnt].push_back(x.u);bccno[x.u]=bcc_cnt;} 72 if(bccno[x.v]!=bcc_cnt){bcc[bcc_cnt].push_back(x.v);bccno[x.v]=bcc_cnt;} 73 if(x.u==u&&x.v==v) break; 74 } 75 } 76 } 77 else if (pre[v]
                      
                       >n && n!=0)120 {121 cas++;122 edgeinit();123 int m=0;124 for(int i=1;i<=n;i++)125 {126 int u,v;127 cin>>u>>v;128 addedge(u,v);addedge(v,u);129 m=max(m,u);m=max(m,v);//最大的点130 }131 find_bcc(m);132 solve(cas,m);133 }134 return 0;135 }