题意：
有一幅图，现在要加一条边，加边之后要你删除一条边，使图不连通，费用为边的费用，要你求的是删除的边的最小值的最大值（每次都可以删除一条边，选最小的删除，这些最小中的最大就为答案）
首先要进行缩点，把图缩为一棵树，因此，加入一条边后图就会存在一个环，环中的任何一条边删除后都不会导致图不连通
之后找一条最小的边，可以说这条边肯定是在加边之后的连通块里的，因为如果不在连通块里，那就直接可以把这条最小的边删掉，而达不到求出答案的目的
找到边后，分别从边的两点开始遍历，要遍历出一条路径来，并且边上的权值要尽可能的小，因为这样才能让不在环中的边尽可能的大，然后，答案就是每个 节点的次小儿子的最小值，如果没有次小儿子就不能算（就是说只有一个儿子，即节点不是三叉的），因为我完全可以把它和最小的边放到一个连通块中，那样答案 就应该更大了。
终上所述：先进行无向图的缩点，再在树上找最小的边，最后分别从边的两点出发，遍历树，找节点的次小儿子节点中的最小值
举个简单的例子（括号内的数字代表边上的权值）1和8间的权值为1，是最小的
1---8
/ \（3）
（2）/ \
2 3
(4) / \(5) (6)/ \(7)
/ \ / \
4 5 6 7
左子树中2的子节点有次小值5，右子树中3的子节点次小值为7，两个次小值间的最小值是5，即答案
现在，比如所你要把3、4连起来。我可以去掉2、5之间的边让图不连通，花费为5
把3、5连起来，我自然可以删掉2、4，花费为4，
一个节点的次小值和最小值（比如说4、5两点）不可能被同时连进一个连通块（或环）中（因为必须把最小的那条边加进环中），正是利用这个性质，不管 把那两个点连起来，我们都可以找到一个最小值或次小值来删掉使图不连通，注意：再重复一遍，同一个节点的最小值和次小值不会被加进同一个环，因此，这些次 小值中的最小的那条边的权值就是答案。（这时你如果把次小的边加进环中，如2--5，自然可以删掉一条更小的边 如2--4 使图不连通，相反，如果没有把次小的边加进去，那次小的就是答案）
思路是次要，代码要能搞出来
1 #include<cstdio> 2 #include<cstring> 3 #include<stack> 4 #include<algorithm> 5 #define N 20100 6 #define M 200100 7 #define inf 100000000 8 #pragma comment(linker, "/STACK:1024000000,1024000000") 9 using namespace std; 10 int head1[N],head2[N],cnt,scc,Min; 11 int dfn[N],low[N],belong[N]; 12 int dp[N]; 13 stack<int>sta; 14 struct Edge{ 15 int v,w,next; 16 }edge[M*4]; 17 18 void addedge(int u,int v,int w,int *head){ 19 edge[cnt].v=v; 20 edge[cnt].w=w; 21 edge[cnt].next=head[u]; 22 head[u]=cnt++; 23 edge[cnt].v=u; 24 edge[cnt].w=w; 25 edge[cnt].next=head[v]; 26 head[v]=cnt++; 27 } 28 void init(int n){ 29 memset(head1,-1,sizeof(head1)); 30 memset(head2,-1,sizeof(head2)); 31 memset(dfn,0,sizeof(dfn)); 32 for(int i=1;i<=n;i++)dp[i]=inf; 33 cnt=scc=0; 34 } 35 void DP(int u,int fa){ 36 int i; 37 for(i=head2[u];i!=-1;i=edge[i].next){ 38 int v=edge[i].v; 39 if(v!=fa){ 40 DP(v,u); 41 dp[v]=min(dp[v],edge[i].w); 42 if(dp[u]>dp[v]){ 43 Min=min(Min,dp[u]); 44 dp[u]=dp[v]; 45 } 46 else 47 Min=min(Min,dp[v]); 48 } 49 } 50 } 51 void tarjan(int u,int fa){ 52 int i,flag=1; 53 dfn[u]=low[u]=dfn[fa]+1; 54 sta.push(u); 55 for(i=head1[u];i!=-1;i=edge[i].next){ 56 int v=edge[i].v; 57 if(v==fa && flag){ 58 flag=0; 59 continue; 60 } 61 if(dfn[v]==0){ 62 tarjan(v,u); 63 low[u]=min(low[u],low[v]); 64 } 65 else 66 low[u]=min(low[u],dfn[v]); 67 } 68 if(dfn[u]==low[u]){ 69 scc++; 70 while(1){ 71 int tem=sta.top(); 72 sta.pop(); 73 belong[tem]=scc; 74 if(tem==u)break; 75 } 76 } 77 } 78 int main(){ 79 int i,n,m; 80 int u,v,w; 81 while(scanf("%d %d",&n,&m)==2){ 82 init(n); 83 for(i=1;i<=m;i++){ 84 scanf("%d %d %d",&u,&v,&w); 85 addedge(u,v,w,head1); 86 } 87 for(i=1;i<=n;i++) 88 if(dfn[i]==0) 89 tarjan(1,0); 90 if(scc==1){ 91 printf("-1\n"); 92 continue; 93 } 94 int last=cnt,whi; 95 Min=inf; 96 for(i=0;i<last;i+=2){ 97 if(belong[edge[i].v]!=belong[edge[i^1].v]){ 98 addedge(belong[edge[i].v],belong[edge[i^1].v],edge[i].w,head2); 99 if(edge[i].w<Min){ 100 whi=i; 101 Min=edge[i].w; 102 } 103 } 104 } 105 Min=inf; 106 DP(belong[edge[whi].v],belong[edge[whi^1].v]); 107 DP(belong[edge[whi^1].v],belong[edge[whi].v]); 108 if(Min==inf)printf("-1\n"); 109 else printf("%d\n",Min); 110 } 111 return 0; 112 }
hdu 4005 双联通 2011大连赛区网络赛E *****
原文：http://www.cnblogs.com/cnblogs321114287/p/4681452.html