?pid=3844
题目描述： 有一座地下的稀有金属矿由n条隧道和一些连接点组成，其中每条隧道连接两个连接点，任意两个连接点之间最多只有一条隧道。为了降低矿工的危险，你的任务是在一些连接点处安装太平井和相应的逃生装置，使得不管哪个连接点倒塌，不在此连接点的所有矿工都能到达太平井逃生（假定除了倒塌的连接点不能通行外，其他隧道和连接点完好无损）。为了节约成本，比应当在尽量少的连接点安装太平井。还需要计算出当太平井的数目最小时的总方案数。
分析： 本题的模型：在一个无向图上选择尽量少的点涂黑，使得任意删除一个点后，每个连通分量至少有一个黑点。不难发现，把割点涂黑是不划算的，，而且在同一个点双连通分量中涂两个黑点也是不划算的。进一步分析发现，当一个点双连通分量只有一个割点时才需要涂，而且是任选一个非割点涂黑
一个特殊情况是整个图没有割点，那么此时只需涂两个点，方案数为n*(n-1)/2 n个数中取两个
这个无限WA了两天，终于发现n*(n-1)溢出了 原来这样写的ans=(ll)(n*(n-1)/2); 应该这样ans=(ll)n*(n-1)/2;
要手动扩栈
ll;const int MAXN=100100;const int MAXM=100010;;int low[MAXN],dfn[MAXN],Stack[MAXN];int dfs_clock,top,block;bool iscut[MAXN];vector<int> bcc[MAXN];struct Edge {int to,next;} edge[MAXM<<1];int head[MAXN],tot;void addedge(int u,int v){edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;}void init(){tot=0;memset(head,0xff,sizeof(head));}void Tarjan(int u,int pre){int v;low[u]=dfn[u]=++dfs_clock;Stack[top++]=u;int son=0;for(int i=head[u]; i!=-1; i=edge[i].next) {v=edge[i].to;if(v==pre) continue;if(!dfn[v]) {son++;Tarjan(v,u);low[u]=min(low[u],low[v]);if(low[v]>=dfn[u]) {iscut[u]=1;block++;bcc[block].clear();int vn;for(;;) {vn=Stack[–top];bcc[block].push_back(vn);if(vn==v) break;}bcc[block].push_back(u);}} else if(low[u]>dfn[v]) {low[u]=dfn[v];}}if(pre<0&&son==1) iscut[u]=false;}void solve(int n){memset(dfn,0,sizeof(dfn));memset(iscut,false,sizeof(iscut));dfs_clock=top=block=0;for(int i=1;i<=n;++i)if(!dfn[i]) Tarjan(i,-1);ll ans1=0,ans2=1;if(block==1) {ans1=2ll;ans2=(ll)n*(n-1)/2;} else {for(int i=1; i<=block; ++i) {int z=bcc[i].size();int cut_cnt=0;for(int j=0; j<z; ++j) {if(iscut[bcc[i][j]]) cut_cnt++;}if(cut_cnt==1) {ans1++;ans2*=(ll)(z-1);}}}printf(“%lld %lld\n”,ans1,ans2);}int main(){#ifndef ONLINE_JUDGEfreopen(“in.cpp”,”r”,stdin);#endif // ONLINE_JUDGEint m,u,v,cas=1;while(scanf(“%d”,&m)&&m) {int n=0;init();while(m–) {scanf(“%d%d”,&u,&v);addedge(u,v);addedge(v,u);n=max(n,max(u,v));}printf(“Case %d: “,cas++);solve(n);}return 0;}
你可能付出一定的代价，但日后你得到的，远比付出的多得多。
