bzoj2730（矿场搭建）

矿场搭建，不知道为什么，莫名其妙T了在212上，额，zyh数据真的坑。

bzoj200轻松跑过啊。

就是点双联通分量缩点，然后标记割点，一个块如果有>=2个割点，则不需要挖矿洞，

如果只有一割点，就乘以改块的大小-1

如果无割点，则乘以C(size,2);

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<vector>

 using namespace std;

 typedef long long ll;

 const int NN=;

 int n,m;

 int tim,top,root,scc;

 int cnt,head[NN],rea[NN*],next[NN*];

 int dfn[NN],low[NN],q[NN],instack[NN],gedian[NN],num[NN];

 vector<int>a[NN];

 void init()

 {

     n=tim=top=scc=;

     memset(head,-,sizeof(head));

     memset(dfn,,sizeof(dfn));

     memset(gedian,,sizeof(gedian));

     memset(num,,sizeof(num));

 }

 void add(int u,int v)

 {

     cnt++;

     next[cnt]=head[u];

     head[u]=cnt;

     rea[cnt]=v;

 }

 void Tarjan(int u,int fa)

 {

     int num=;

     dfn[u]=low[u]=++tim;

     q[++top]=u,instack[u]=;

     for (int i=head[u];i!=-;i=next[i])

     {

         int v=rea[i];

         if (v==fa) continue;

         if (dfn[v]==)

         {

             Tarjan(v,u);

             low[u]=min(low[u],low[v]);

             num++;

             if (u==root&&num>) gedian[u]=;

             else if (u!=root&&low[v]>=dfn[u]) gedian[u]=;

             if (low[v]>=dfn[u])

             {

                 scc++;

                 a[scc].clear();

                 int x=-;

                 while (x!=u)

                 {

                     x=q[top--];

                     instack[x]=;

                     a[scc].push_back(x);

                 }

                 q[++top]=u,instack[u]=;

             }

         }

         else low[u]=min(low[u],dfn[v]);

     }

 }

 long long c(int n,int m)

 {

     long long res=n*(n-)/;

     return res;

 }

 int main()

 {

     int fzy=;

     while(scanf("%d",&m)&&m)

     {

         fzy++;

         init();

         int x,y;

         for (int i=;i<=m;i++)

         {

             scanf("%d%d",&x,&y);

             add(x,y),add(y,x);

             n=max(x,n),n=max(y,n);

         }

         for (int i=;i<=n;i++)

             if (dfn[i]==)

             {

                 root=i;

                 Tarjan(i,-);

             }

         for (int i=;i<=scc;i++)

             for (int j=;j<a[i].size();j++)

                 if (gedian[a[i][j]]) num[i]++;

         long long ans1=,ans2=;

         for (int i=;i<=scc;i++)

         {

             if (num[i]==)

             {

                 ans1+=;

                 ans2*=c(a[i].size(),);

             }

             else if (num[i]==)

                  {

                       ans1+=;

                       ans2*=a[i].size()-;

                  }

         }

         printf("Case %d: %lld %lld\n",fzy,ans1,ans2);

     }

     return ;

 }