HNOI2012矿场搭建

lovesickman

于 2022-07-24 14:55:15 发布

阅读量349

点赞数

分类专栏： # Luogu图论文章标签： c++ 算法开发语言

本文链接：https://blog.csdn.net/hacker__man/article/details/125959256

版权

Luogu图论专栏收录该内容

7 篇文章

订阅专栏

该博客讨论了一种无向图问题，其中要求在节点坍塌时确保其他节点能从出口逃脱。通过Tarjan算法求解图的强连通分量，并确定最少的救援出口数量。博客中还提到了疑似算法实现的错误，并给出了完整的C++代码示例来解决这个问题。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

HNOI2012矿场搭建

题意

给定一个无向图，可能不连通，如果图中某个点坍塌，要求其他点一定能从某个出口逃出，问:至少设计几个出口和不同的最小救援出口的设置数量。

貌似发现了蓝书上(P404)求low数组的错误(雾)

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;

const int N=510*2,M=1010;

int n,m,h[N],ne[M],e[M],idx;
int dfn[N],low[N],tim;
int stack[N],top;
vector<int>dcc[N];
int dcc_cnt,root;
bool cut[N];

void add(int a,int b)
{
   e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int x)
{
   low[x]=dfn[x]=++tim;
   stack[++top]=x;
   
   if(x==root&&h[x]==-1)
   {
       dcc[++dcc_cnt].push_back(x);
       return ;
   }
   int cnt=0;
   for(int i=h[x];~i;i=ne[i])
   {
       int j=e[i];
       if(!dfn[j])
       {
           tarjan(j);
           low[x]=min(low[x],low[j]);
           if(dfn[x]<=low[j])
           {
               cnt++;
               if(x!=root||cnt>1)
                   cut[x]=true;
               int y;
               dcc_cnt++;
               do{
               
                   y=stack[top--];
                   dcc[dcc_cnt].push_back(y);
               }while(y!=j);
               dcc[dcc_cnt].push_back(x);
           }
       }
       else low[x]=min(low[x],dfn[j]);
   }
}

int main()
{
   int t=1;
   while(cin>>m,m)
   {
       for(int i=1;i<=dcc_cnt;i++)
           dcc[i].clear();
       idx=tim=top=dcc_cnt=n=0;
       memset(h,-1,sizeof h);
       memset(dfn,0,sizeof dfn);
       memset(cut,0,sizeof cut);
       while(m--)
       {
           int a,b;cin>>a>>b;
           add(a,b),add(b,a);
           n=max(n,a),n=max(n,b);
       }
       for(root=1;root<=n;root++)
           if(!dfn[root])
               tarjan(root);
       
       int res=0;
       unsigned long long num=1;
       cout<<dcc_cnt<<endl;
       cout<<"---"<<endl;
       for(int i=1;i<=n;i++)
           cout<<i<<" "<<dfn[i]<<" "<<low[i]<<endl;
       cout<<endl;
       for(int i=1;i<=dcc_cnt;i++)
       {
           int cnt=0;
           for(int j=0;j<dcc[i].size();j++)
           {
               if(cut[dcc[i][j]])
                   cnt++;
           }
           if(cnt==0)
           {
               if(dcc[i].size()>1)
                   res+=2,num*=dcc[i].size()*(dcc[i].size()-1)/2;
               else
                   res++;
           }
           else if(cnt==1)
               res++,num*=dcc[i].size()-1;
           cout<<"cnt="<<cnt<<endl;
       }
       printf("Case %d: %d ",t++,res);
       cout<<num<<endl;
       cout<<top<<" "<<stack[top]<<endl;
   }
   return 0;
}