題目鏈接：https://vjudge.net/problem/HDU-4738
題目：tarjan求橋，坑點：
題目說是分島任務...如果所有島之間沒有完全連通，就不需要執行任務了...答案直接是0...
橋上可能沒人，但是，炸彈需要一個人去送，所以至少1個人，
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 using namespace std; 5 6 const int N = (int)1e3+10; 7 int n,m,tot,tim,solders; 8 int head[N],low[N],dfn[N]; 9 struct node{ 10 int to,nxt,w; 11 }e[(N*N)<<1]; 12 13 void init(){ 14 for(int i = 0; i <= n; ++i){ 15 head[i] = -1; dfn[i] = 0; 16 } 17 tot = tim = 0; 18 solders = (int)1e6; 19 } 20 21 inline void add(int u,int v,int w){ 22 e[tot].to = v; e[tot].w = w; e[tot].nxt = head[u]; head[u] = tot++; 23 } 24 25 void tarjan(int now,int pre){ 26 dfn[now] = low[now] = ++tim; 27 int to,pre_cnt = 0; 28 for(int o = head[now]; ~o; o = e[o].nxt){ 29 to = e[o].to; 30 if(to == pre && pre_cnt == 0){ pre_cnt = 1; continue; }//重邊處理 31 if(!dfn[to]){ 32 tarjan(to,now); 33 low[now] = min(low[now],low[to]); 34 if(dfn[now] < low[to]) solders = min(solders,e[o].w); 35 }else low[now] = min(low[now],dfn[to]); 36 } 37 } 38 39 int main(){ 40 41 int u,v,w; 42 while(~scanf("%d%d",&n,&m) && (n+m)){ 43 init(); 44 for(int i = 0;i < m; ++i){ 45 scanf("%d%d%d",&u,&v,&w); 46 add(u,v,w); add(v,u,w); 47 } 48 tarjan(1,1); 49 for(int i = 1;i <= n; ++i){ 50 if(!dfn[i]){ solders = -2; break; }//島本來就是分的 51 } 52 if(solders == -2) printf("0\n"); 53 else{ 54 if(solders == (int)1e6) solders = -1;//沒法完成任務 55 printf("%d\n",!solders ? 1:solders); 56 } 57 } 58 59 return 0; 60 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/106064.html
標籤：其他
下一篇：括號匹配（堆疊）