題目:

煤礦工地可以看成是由隧道連接挖煤點組成的無向圖。為安全起見，希望在工地發(fā)生事故時所有挖煤點的工人都能有一條出路逃到救援出口處。于是礦主決定在某些挖煤點設立救援出口，使得無論哪一個挖煤點坍塌之后，其他挖煤點的工人都有一條道路通向救援出口。

請寫一個程序，用來計算至少需要設置幾個救援出口，以及不同最少救援出口的設置方案總數(shù)。

大意:

求 在一個無向圖中放若干特殊點 使刪除任意一個節(jié)點后剩下的每一個連通塊中都有特殊點的最小特殊點個數(shù)與方案數(shù)

思路:

若刪除的點不是割點 則對整張圖無影響

若是割點 則圖被分為若干連通塊 每個連通塊中都必須有特殊點

由于只有刪除割點時才會影響圖的連通塊個數(shù)所以這里將圖簡化 變?yōu)橐粋€個點復連通分量通過共有割點相連

很容易發(fā)現(xiàn) 若一個點復連通分量內只有一個割點 那么該割點刪除后該分量將獨立出去 故必須有一個特殊點

因為只有一個割點的點復連通分量至少有2個 即原連通圖至少有2個特殊點 刪除一個割點 原圖最終至少剩下一個特殊點 所以有兩個及以上割點的點復連通分量不會受到影響

0個割點時 要保留兩個特殊點 刪掉一個特殊點怎么玩？

至此算法已經顯然易見了

下面是代碼：

?

1 #include <cstdio> 2 #include <iostream> 3 #include <memory.h> 4 #define MAXX 600 5 #define MAX(a,b) (a>b?a:b) 6 #define MIN(a,b) (a<b?a:b) 7 #define r(x) x=read() 8 using namespace std; 9 typedef long long ll; 10 int fi,flag[MAXX],dfn[MAXX],low[MAXX],k,n,u,to, 11 cnt,sta[MAXX],ans2=0,top,num,id[MAXX][MAXX],T[MAXX],h[MAXX],t; 12 ll ans=1; 13 int read() 14 { 15 char ch=0;int w=0; 16 while(ch<'0'||ch>'9'){ch=getchar();} 17 while(ch>='0'&&ch<='9'){w=w*10+ch-'0';ch=getchar();} 18 return w; 19 } 20 struct edge{int to,nex;}e[MAXX<<3]; 21 void add(int u,int to) 22 { 23 cnt++; 24 e[cnt]=(edge){to,h[u]}; 25 h[u]=cnt; 26 } 27 void tarjan(int now) 28 { 29 int tot=0,sign=0; 30 dfn[now]=low[now]=++k; 31 sta[++top]=now; 32 for(int i=h[now];i;i=e[i].nex) 33 { 34 if(!dfn[e[i].to]) 35 { 36 tot++,tarjan(e[i].to),low[now]=MIN(low[now],low[e[i].to]); 37 if((fi==now&&tot>1)||(low[e[i].to]>=dfn[now]&&fi!=now)) 38 flag[now]=1; 39 if(dfn[now]<=low[e[i].to]) 40 { 41 num++; 42 while(sta[top]!=now) 43 { 44 id[num][++T[num]]=sta[top]; 45 top--; 46 } 47 id[num][++T[num]]=now; 48 } 49 } 50 else 51 low[now]=MIN(low[now],dfn[e[i].to]); 52 } 53 } 54 void solve() 55 { 56 memset(h,0,sizeof(h)); 57 memset(dfn,0,sizeof(dfn)); 58 memset(T,0,sizeof(T)); 59 memset(flag,0,sizeof(flag)); 60 memset(low,0,sizeof(low)); 61 ans=1,top=0,k=0,ans2=0,cnt=0,num=0; 62 r(n); 63 if(n==0) exit(0); 64 for(int i=1;i<=n;++i) 65 r(u),r(to),add(u,to),add(to,u); 66 for(int i=1;i<=500;++i) 67 if(h[i]&&!dfn[i]) 68 fi=i,tarjan(i); 69 for(int i=1;i<=num;++i) 70 { 71 int len=T[i],z=0; 72 for(int j=1;j<=len;++j) 73 { 74 if(flag[id[i][j]]) z++; 75 } 76 if(z==0) ans2+=2,ans=ans*len*(len-1)/2; 77 else if(z==1) ans2++,ans=ans*(len-1); 78 } 79 printf("Case %d: %d %lld\n",t,ans2,ans); 80 } 81 int main() 82 { 83 while(1){t++;solve();} 84 return 0; 85 }

?

轉載于:https://www.cnblogs.com/dah1314/p/10890782.html

總結

以上是生活随笔為你收集整理的Tarjan水题系列(2):HNOI2012 矿场搭建的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。