题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4738
题意：有n座岛和m条桥，每条桥上有w个兵守着，现在要派不少于守桥的士兵数的人去炸桥，只能炸一条桥，使得这n座岛不连通，求最少要派多少人去。
分析：只需要用Tarjan算法求出图中权值最小的那条桥就行了。但是这题有神坑。
第一坑：如果图不连通，不用派人去炸桥，直接输出0
第二坑：可能会有重边
第三坑：如果桥上没有士兵守着，那至少要派一个人去炸桥。
比赛的时候看完就想做了，但是图论太挫了，居然不会求桥，结果梓铭大神一下子就把代码敲好了，但是苦于题目有神坑，交了几次wa后，突然醒悟，才把题目AC了。
AC代码：
1 #include<stdio.h> 2 #include<string.h> 3 const int N=1000+5; 4 struct EDGE{ 5 int v,w,next; 6 }edge[N*N*2]; 7 int first[N],low[N],dfn[N],vis[N]; 8 int g,cnt,sum,ans; 9 int min(int a,int b) 10 { 11 return a<b?a:b; 12 } 13 void AddEdge(int u,int v,int w) 14 { 15 edge[g].v=v; 16 edge[g].w=w; 17 edge[g].next=first[u]; 18 first[u]=g++; 19 } 20 void Tarjan(int u,int fa) 21 { 22 int i,v; 23 low[u]=dfn[u]=++cnt; 24 for(i=first[u];i!=-1;i=edge[i].next) 25 { 26 v=edge[i].v; 27 // if(v==fa) 28 // continue; 29 if(i==(fa^1)) 30 continue; 31 if(!dfn[v]) 32 { 33 Tarjan(v,i); 34 low[u]=min(low[u],low[v]); 35 if(low[v]>dfn[u]) 36 { 37 if(edge[i].w<ans) 38 ans=edge[i].w; 39 } 40 } 41 else 42 low[u]=min(low[u],dfn[v]); 43 } 44 } 45 void dfs(int u) 46 { 47 if(vis[u]) 48 return ; 49 vis[u]=1; 50 sum++; 51 for(int i=first[u];i!=-1;i=edge[i].next) 52 dfs(edge[i].v); 53 } 54 int main() 55 { 56 int i,n,m,u,v,w; 57 while(scanf("%d%d",&n,&m)) 58 { 59 if(n==0&&m==0) 60 break; 61 g=cnt=0; 62 memset(first,-1,sizeof(first)); 63 memset(dfn,0,sizeof(dfn)); 64 memset(vis,0,sizeof(vis)); 65 while(m--) 66 { 67 scanf("%d%d%d",&u,&v,&w); 68 AddEdge(u,v,w); 69 AddEdge(v,u,w); 70 } 71 sum=0; 72 dfs(1); 73 if(sum<n) 74 { 75 printf("0 "); 76 continue; 77 } 78 ans=1000000; 79 // for(i=1;i<=n;i++) 80 // if(!dfn[i]) 81 // Tarjan(i,0); 82 Tarjan(1,-1); 83 if(ans==1000000) 84 printf("-1 "); 85 else 86 { 87 if(ans==0) 88 ans=1; 89 printf("%d ",ans); 90 } 91 } 92 return 0; 93 }