题面
1521：【 例 2】矿场搭建
一句话题意：一个图中，求最少的“出口”的个数，使得任意去掉一个点，其他点总能走到出口。
思路：
用Tarjin缩点求双连通分量，再对双连通分量的情况讨论求答案。
Tarjin缩点求双连通分量，请看我的另一篇文章。这里直接给出代码。
stack<int> st;
void tarjin(int k)
{
low[k]=dfn[k]=++tot,st.push(k);
int cntt=0;
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to])
{
tarjin(a[i].to),cntt++,low[k]=min(low[k],low[a[i].to]);
if((k==rt&&cntt>1)||(k!=rt&&low[a[i].to]>=dfn[k]))
cp[k]=1;//割点
if(low[a[i].to]>=dfn[k]) //双连通块
{
co[++num].clear();
do co[num].push_back(st.top()),st.pop();
while (st.top()!=k);
co[num].push_back(k);
}
}
else low[k]=min(low[k],dfn[a[i].to]);
}
然后对每个双连通分量，统计割点数量进行讨论。
首先，我们需要知道，如果一张图只有一个双连通分量，就没有割点；否则每个双连通分量种中至少有一个割点。
所以可以讨论了，设这个双连通分量大小为size：
①只有一个双连通分量（即没有割点），。
②只有一个割点，因此这个割点一被去掉，就会让这个双连通分量出不去，即这个双连通分量里面得有一个出口，因此。
③有两个及以上割点，因此一个割点被毁，它可以逃到别的出口去，ans1，ans2不变。
for(int i=1; i<=num; i++)
{
int tott=0,len=co[i].size();
for(int j=0; j<len; j++) tott+=cp[co[i][j]];
if(tott==0) ans1+=2,ans2=ans2*len*(len-1)/2;
else if(tott==1) ans1++,ans2=ans2*(len-1);
}
printf("Case %d: %lld %lld\n",++ca,ans1,ans2);
最后提一嘴清空，东西很多都得清空，所以我在这里错了很久。
memset(head,0,sizeof(head)),cnt=tot=num=n=ans1=0,ans2=1,memset(cp,0,sizeof(cp));
memset(co,0,sizeof(co)),memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low));//注意清零
while(!st.empty()) st.pop();
代码
直接上代码
#include <bits/stdc++.h>
using namespace std;
int ca,n,m,x,y,rt;
int head[505],cnt;
int dfn[1005],low[1005],num,tot;
vector<int> co[505];
long long ans1,ans2;
struct node
{
int to,nxt;
} a[1005];
bool cp[1005];//cut point 割点
void add(int x,int y)
{
a[++cnt].to=y,a[cnt].nxt=head[x],head[x]=cnt;
}
stack<int> st;
void tarjin(int k)
{
low[k]=dfn[k]=++tot,st.push(k);
int cntt=0;
for(int i=head[k]; i; i=a[i].nxt)
if(!dfn[a[i].to])
{
tarjin(a[i].to),cntt++,low[k]=min(low[k],low[a[i].to]);
if((k==rt&&cntt>1)||(k!=rt&&low[a[i].to]>=dfn[k]))
cp[k]=1;//割点
if(low[a[i].to]>=dfn[k]) //双连通块
{
co[++num].clear();
do co[num].push_back(st.top()),st.pop();
while (st.top()!=k);
co[num].push_back(k);
}
}
else low[k]=min(low[k],dfn[a[i].to]);
}
int main()
{
scanf("%d",&m);
while(m!=0)
{
memset(head,0,sizeof(head)),cnt=tot=num=n=ans1=0,ans2=1,memset(cp,0,sizeof(cp));
memset(co,0,sizeof(co)),memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low));//注意清零
while(!st.empty()) st.pop();
for(int i=1; i<=m; i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x),n=max(n,max(x,y));
for(int i=1; i<=n; i++) if(!dfn[i]) rt=i,tarjin(i);
for(int i=1; i<=num; i++)
{
int tott=0,len=co[i].size();
for(int j=0; j<len; j++) tott+=cp[co[i][j]];
if(tott==0) ans1+=2,ans2=ans2*len*(len-1)/2;
else if(tott==1) ans1++,ans2=ans2*(len-1);
}
printf("Case %d: %lld %lld\n",++ca,ans1,ans2);
scanf("%d",&m);
}
return 0;
}
小结
先说思路，思路是很基础的，可能分析后面的需要花一些时间。
然后是代码，这个代码我也是修修补补（所以长得丑），很难打，得有点代码功底。
最后是吐槽，这个数据太水了，所以我一开始才WA了两个点……格式太烦了，也烦了我很久。还有是清空，又是烦人的东西。
牢骚发完，欢迎私信提问。
完结撒花！！！
别忘了点赞，关注，谢谢！！
