loj10099 矿场搭建-白红宇

loj10099 矿场搭建

阅读量：6331 次

发布时间：2019-06-22

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

分析

我们发现可以将这张图转换为一个联通块来处理。我们求出所有的割点。在求完之后我们我们对于每一个点双连通分量如果它没有割点相连则需要布置两个出口，因为可能有一个出口正好被割掉。而如果有一个割点我们只需要布置一个出口就行了，因为如果割掉割点可以从出口出去而如果割掉出口便可以通过割点到别的联通块中从而出去。而如果大于等于两个割点则无论如何都可以出去。至于方案数用组合数随便做一下就行了。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;long long dfn[520],low[520],is[520],cnt,n,m,ans,minn,vis[520],T,tot,siz;map
                   
                    id;vector
                    
                     v[520];inline void init(){ for(int i=0;i<=500;i++)v[i].clear(); id.clear(); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(is,0,sizeof(is)); memset(vis,0,sizeof(vis)); ans=1; minn=0; cnt=0; n=0; T=0;}inline void tarjan(long long x,long long fa){ dfn[x]=low[x]=++cnt; long long son=0; for(long long i=0;i
                     
                      =dfn[x])is[x]=1; }else low[x]=min(low[x],dfn[v[x][i]]); } if(!fa&&son==1)is[x]=0; return;}inline void work(long long x){ siz++; vis[x]=T; for(long long i=0;i

转载于:https://www.cnblogs.com/yzxverygood/p/9525096.html

你可能感兴趣的文章