题意：给一个无向图，敌人还可以再随机建一条边，而你可以拆掉一条边并产生一定的花费。问至少要多少花费才能保证拆掉一条边之后图不联通。

tarjan缩点。。。。如果最大度<=2。。。则在加一条边后构成一整个强连通分量是无解的

否则找最小的某个节点的到子节点的第3小边（第1小，和第2小的边是可能被连到一起的），具体做法：重新构图的时候找到最小的边，然后从最小的边的两个端点分别dfs找第二小的边。。。

注意可能出现重边，建图的时候要给每个边加上编号，方便判断。。。

The war

3 2
1 2 1
2 3 2
4 3
1 2 1
1 3 2
1 4 3

-1
3

Hint
For the second sample input: our enemy may build line 2 to 3, 2 to 4,

3 to 4. If they build line 2 to 3, we will destroy line 1 to 4, cost 3. If they

build line 2 to 4, we will destroy line 1 to 3, cost 2. If they build line 3 to 4,

we will destroy line 1 to 2, cost 1. So, if we want to make sure that we can

destroy successfully, the minimum cost is 3. 
 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int INF=0x3f3f3f3f;
const int maxn2=200200;
const int maxn1=10100;

int n,m;

struct Edge
{
    int from,to,next,val,id;
}edge[maxn2],edge2[maxn2];

int Size,Adj[maxn1],Size2,Adj2[maxn1];
int degree[maxn1],dp[maxn1][2],ANS;
bool use[maxn2];

void init()
{
    Size=0; memset(Adj,-1,sizeof(Adj));
}

void Add_Edge(int u,int v,int cost,int d)
{
    edge[Size].to=v;
    edge[Size].from=u;
    edge[Size].id=d;
    edge[Size].val=cost;
    edge[Size].next=Adj[u];
    Adj[u]=Size++;
}

void init2()
{
    Size2=0; memset(Adj2,-1,sizeof(Adj2));
}

void Add_Edge2(int u,int v,int cost)
{
    edge2[Size2].to=v;
    edge2[Size2].from=u;
    edge2[Size2].val=cost;
    edge2[Size2].next=Adj2[u];
    Adj2[u]=Size2++;
}

/****************tarjan**********************/

int Low[maxn1],DFN[maxn1],Stack[maxn1],Belong[maxn1];
int Index,top,scc;

bool Instack[maxn1];

void tarjan(int u,int fa)
{
    int v;
    Low[u]=DFN[u]=++Index;
    Stack[top++]=u; Instack[u]=true;
    for(int i=Adj[u];~i;i=edge[i].next)
    {
        v=edge[i].to;
        if(v==fa&&use[edge[i].id]) continue;
        use[edge[i].id]=1;
        if(!DFN[v])
        {
            tarjan(v,u);
            Low[u]=min(Low[u],Low[v]);
        }
        if(Instack[v])
        {
            Low[u]=min(Low[u],DFN[v]);
        }
    }

    if(Low[u]==DFN[u])
    {
        scc++;
        do
        {
            v=Stack[--top];
            Instack[v]=false;
            Belong[v]=scc;
        }while(v!=u);
    }
}

void scc_solve(int n)
{
    memset(DFN,0,sizeof(DFN));
    memset(Instack,false,sizeof(Instack));

    Index=scc=top=0;

    memset(use,0,sizeof(use));
    for(int i=1;i<=n;i++) if(!DFN[i]) tarjan(i,i);
}

int dfs(int u,int f)
{

    for(int i=Adj2[u];~i;i=edge2[i].next)
    {
        int v=edge2[i].to;
        if(v==f) continue;
        int mini=edge2[i].val;
        mini=min(mini,dfs(v,u));
        if(mini<=dp[u][0])
        {
            dp[u][1]=dp[u][0];
            dp[u][0]=mini;
        }
        else if(mini<=dp[u][1])
        {
            dp[u][1]=mini;
        }
        ANS=min(ANS,dp[u][1]);
    }
    return dp[u][0];
}

int main()
{

    while(scanf("%d%d",&n,&m)!=EOF)
    {
        init(); init2();
        for(int i=0;i<m;i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            Add_Edge(a,b,c,i);
            Add_Edge(b,a,c,i);
        }

        scc_solve(n);

        int minedge=-1,mark=INF,maxd=-INF;
        memset(degree,0,sizeof(degree));

        for(int i=0;i<Size;i++)
        {
            int u=edge[i].from;
            int v=edge[i].to;
            int c=edge[i].val;
            if(Belong[u]!=Belong[v])
            {
                Add_Edge2(Belong[u],Belong[v],c);
                degree[Belong[u]]++,degree[Belong[v]]++;
                maxd=max(maxd,max(degree[Belong[u]],degree[Belong[v]]));
                if(mark>c)
                {
                    mark=c;
                    minedge=i;
                }
            }
        }

        if(maxd<=4)
        {
            puts("-1"); continue;
        }

        memset(dp,63,sizeof(dp)); ANS=INF;

        dfs(Belong[edge[minedge].from],Belong[edge[minedge].to]);
        dfs(Belong[edge[minedge].to],Belong[edge[minedge].from]);

        printf("%d\n",ANS);

    }
    return 0;
}

HDOJ 4005 The war,布布扣,bubuko.com

HDOJ 4005 The war

原文：http://blog.csdn.net/ck_boss/article/details/23276161