题目传送门

因为这道题的点会崩塌,所以就可以用“点不重复路径”的点双来做了

简单做下分析:

对于点双中没有割点的情况来说

需要建立2个救援出口,因为有可能救援出口所在的点坍塌,这时就需要另一个出口了

这一个点可以是点双中的任意两个点

出口数量+2,方案数*(点双中节点个数)*(点双中节点个数-1)/2

对于点双中有一个割点的情况来说

红圈中的便是一个点双

只需建立一个救援出口即可,因为即使建好的出口坍塌,也可以通过割点到达其他点双,如果割点坍塌,就可以通过点双内部的出口逃离(即出口不能建立在割点上)

出口数量+1,方案数*(点双中的节点个数-1)

对于点双中有两个以上的割点的情况来说

 红圈中的便是一个点双

一个出口都不用建立,因为不管是哪个节点坍塌,都可以从割点走到其他点双从而逃脱

出口数量不变,方案数不变

注意:这道题初始化极其恶心,要再三检查

上代码~

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 typedef long long ll;
  4 ll n,m;// 点的个数 边的个数
  5 ll head[100005];// 以i为起点的第一条边
  6 ll cnt;// 边数(临接表)
  7 ll js;// 搜索时间截
  8 ll cut[100005],ct;// 是否为割点 割点个数
  9 ll ans=1;// 方案数
 10 ll flag;// 见下方代码中有解释
 11 ll gs;// 出口个数
 12 ll dfn[100005];// 搜索序
 13 ll low[100005];// i所在的点双中,搜索序最小值
 14 ll rt;// 当前根节点
 15 ll ch;// 当前根节点的子树个数
 16 struct edge
 17 {
 18     ll v,nxt;
 19 }e[50005];//链式前向星临接表存图
 20 void add(ll u,ll v)
 21 {
 22     ++cnt;
 23     e[cnt].v=v;
 24     e[cnt].nxt=head[u];
 25     head[u]=cnt;
 26 }//添加一条边
 27 inline ll read()
 28 {
 29     ll x=0,f=1; char c=getchar();
 30     while(c<'0'||c>'9') {if(c=='-') f=0; c=getchar();}
 31     while(c>='0'&&c<='9') {x=x*10+c-'0'; c=getchar();}
 32     return f?x:-x;
 33 }//快读
 34 stack<ll> s;
 35 vector<ll> f[10005];// 存储点双
 36 ll fl; // 点双个数
 37 inline void tarjan(ll u,ll fa)
 38 {
 39     dfn[u]=low[u]=++js;
 40     s.push(u);
 41     for(ll i=head[u];i;i=e[i].nxt)
 42     {
 43         ll v=e[i].v;
 44         if(!dfn[v])
 45         {
 46             tarjan(v,u);
 47             low[u]=min(low[u],low[v]);
 48             if(low[v]>=dfn[u])
 49             {
 50                 ++fl;
 51                 while(s.top()!=v)
 52                     f[fl].push_back(s.top()),s.pop();
 53                 f[fl].push_back(s.top()),s.pop();
 54                 f[fl].push_back(u);
 55                 if(!cut[u]&&u!=rt)
 56                 {
 57                     ct++;
 58                     cut[u]=1;
 59                 }
 60                 if(u==rt) ch++;
 61             }
 62         }
 63         else if(v!=fa) low[u]=min(low[u],dfn[v]);
 64     }
 65     if(u==rt&&ch>=2)
 66     {
 67         if(!cut[u]) ct++;
 68         cut[u]=1;
 69     }//根节点为割点的情况
 70 }
 71 int main()
 72 {
 73     ll a,b;
 74     ll faq=0;//第几组测试数据
 75     while(1)
 76     {
 77         ++faq;
 78         ch=0;//这个没有必要,懒得删了
 79         memset(e,0,sizeof(e));
 80         n=0;
 81         cnt=0;
 82         memset(head,0,sizeof(head));
 83         js=0;
 84         ct=0;
 85         memset(cut,0,sizeof(cut));
 86         ans=1;
 87         gs=0;
 88         for(ll i=1;i<=fl;i++) f[i].clear();
 89         fl=0;
 90         memset(dfn,0,sizeof(dfn));
 91         memset(low,0,sizeof(low));//以上为初始化
 92         m=read(); if(m==0) break;
 93         for(ll i=1;i<=m;i++)
 94         {
 95             a=read(); b=read();
 96             n=max(n,a); n=max(n,b);//找到此题中编号最大的点(可以理解为点数)
 97             add(a,b);
 98             add(b,a);
 99         }
100         for(ll i=1;i<=n;i++)
101             if(!dfn[i])
102             {
103                 rt=i; ch=0;
104                 tarjan(i,-1);
105                 while(!s.empty()) s.pop();//图不连通,注意每个点都要搜
106             }
107         for(ll i=1;i<=fl;i++)
108         {
109             flag=0;
110             ll p=f[i].size();
111             for(ll j=0;j<p;j++)
112                 if(cut[f[i][j]]) flag++;//flag为点双中割点数
113             if(flag==0) ans*=(f[i].size())*(f[i].size()-1)/2,gs+=2;
114             if(flag==1) ans*=(f[i].size()-1),++gs;//统计答案
115         }
116         cout<<"Case "<<faq<<": "<<gs<<' '<<ans<<endl;
117     }
118     return 0;
119 }
120 /*
121 5
122 1 2
123 2 3
124 1 3
125 3 4
126 1 4
127 0
128 */
01-05 03:42