　　　　　　　　　　　　Caocao's Bridges

　　　　　　　　　　　　　　Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
　　　　　　　　　　　　　　　　　　　　Total Submission(s): 5050 Accepted Submission(s): 1584

Problem Description

Caocao was defeated by Zhuge Liang and Zhou Yu in the battle of Chibi. But he wouldn't give up. Caocao's army still was not good at water battles, so he came up with another idea. He built many islands in the Changjiang river, and based on those islands, Caocao's army could easily attack Zhou Yu's troop. Caocao also built bridges connecting islands. If all islands were connected by bridges, Caocao's army could be deployed very conveniently among those islands. Zhou Yu couldn't stand with that, so he wanted to destroy some Caocao's bridges so one or more islands would be seperated from other islands. But Zhou Yu had only one bomb which was left by Zhuge Liang, so he could only destroy one bridge. Zhou Yu must send someone carrying the bomb to destroy the bridge. There might be guards on bridges. The soldier number of the bombing team couldn't be less than the guard number of a bridge, or the mission would fail. Please figure out as least how many soldiers Zhou Yu have to sent to complete the island seperating mission.

Input

There are no more than 12 test cases.

In each test case:

The first line contains two integers, N and M, meaning that there are N islands and M bridges. All the islands are numbered from 1 to N. ( 2 <= N <= 1000, 0 < M <= N² )

Next M lines describes M bridges. Each line contains three integers U,V and W, meaning that there is a bridge connecting island U and island V, and there are W guards on that bridge. ( U ≠ V and 0 <= W <= 10,000 )

The input ends with N = 0 and M = 0.

Output

For each test case, print the minimum soldier number Zhou Yu had to send to complete the mission. If Zhou Yu couldn't succeed any way, print -1 instead.

Sample Input

3 3
1 2 7
2 3 4
3 1 4
3 2
1 2 7
2 3 4
0 0

Sample Output

-1 4

题目：

周宇要炸调曹操的岛屿网络，是他们不相连，但是他只有一枚炸弹，所以他只能摧毁一座桥。周宇必须派一个人带炸弹来摧毁这座桥。桥上可能有守卫。轰炸队的士兵数量不能少于桥梁的守卫人数，否则任务将失败。请找出至少有多少士兵周宇要送到岛分离任务完成。

思路：

求出割边，求出边权最小的割边。如果没有割边，则无法完成任务，输出-1，如果割边不为1，我们求最小的割边的边权

有特殊情况要判断

1.这个图不一定是连通的，这样我们就不用去炸了

2.这个桥上可能没有人，但是我们还是要派一个人去炸桥

3.这个图没有割点，那就无法完成任务，输出-1

代码：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 1000010
using namespace std;
int n,m,x,y,z,s,tim,tot,ans=N;
int dfn[N],low[N],vis[N],head[N],cut_edge[N],cut_point[N];
struct Edge
{
    int from,to,next,dis;
}edge[N];
int read()
{
    ,f=; char ch=getchar();
    ; ch=getchar();}
    +ch-'; ch=getchar();}
    return x*f;
}
int add(int x,int y,int z)
{
    tot++;
    edge[tot].to=y;
    edge[tot].dis=z;
    edge[tot].next=head[x];
    head[x]=tot;
}
int  tarjan(int now,int pre)
{
    ; bool boo=false; vis[now]=true;
    dfn[now]=low[now]=++tim;
    for(int i=head[now];i;i=edge[i].next)
    {
        int t=edge[i].to;
        )==i) continue;
        if(!dfn[t])
        {
            sum++;tarjan(t,i);
            low[now]=min(low[now],low[t]);
            if(low[t]>dfn[now]) ans=min(ans,edge[i].dis);
        }
        else
          low[now]=min(low[now],dfn[t]);
    }
    s++;
}
void clean()
{
    ans=N,tim=,tot=,s=;
    memset(dfn,,sizeof(dfn));
    memset(low,,sizeof(low));
    memset(vis,,sizeof(vis));
    memset(head,,sizeof(head));
    memset(cut_edge,,sizeof(cut_edge));
}
int main()
{
    )
    {
        n=read(),m=read();
        clean();
        &&m==) break;
        ;i<=m;i++)
         x=read(),y=read(),z=read(),add(x,y,z),add(y,x,z);
        tarjan(,);
        if(s<n) printf("0\n");
        else if(ans==N) printf("-1\n");
        ) printf("1\n");
        else printf("%d\n",ans);
    }
    ;
}

巴特西

HDU——4738 Caocao's Bridges

Caocao's Bridges

最新文章

热门文章