HDU 4738 Caocao's Bridges(重边无向图求桥)

HDU 4738 Caocao's Bridges(重边无向图求桥)

http://acm.hdu.edu.cn/showproblem.php?pid=4738

题意:给你一个无向图(可能有重边),然后图中的每条边有数量不定的守卫,现在你需要去炸毁一条图中的桥.问你最少需要派多少人去?(人数要>=桥边的守卫数目).

分析:

本题的本质还是无向图求桥,但是本题有3个点要注意:

1.所给的图可能不连通,且不连通的时候不需要炸,输出0.

2.当所要去炸的桥上的守卫数=0时,我们需要派的人数是1不是0.

3.任意两个节点u与v之间可能存在多条边.

对于上面的1与2点,我们在原始tarjan()函数后加点判断就能解决.不过对于重边无向图,首先我们要用邻接表来保存图了(不能再用vector的邻接矩阵了).其次在tarjan()函数的for循环中:

这句if(v==fa) continue; 需要改改了.因为比如节点u与节点v之间有两条(重)边.v节点可以通过第二条与u相连的边回到u使得low[v]的值==low[u]的值.(所以这样看来,就算是有重边存在,一个边双连通分量中的所有点low[i]值依然相同)

这里我们要知道,v虽然不能通过从u到v的边1回到u,但是可以通过u与v之间相连的边2回到u.对于这种情况,我们是这么实现的:

把每条无向边分为两条有向边i与i+1,如果u通过边i到达了v,那么v中必然有一条边是i^1且可以通过该i^1边到u.所以如果在v节点遍历时到达i^1边时,我们直接跳过.

具体实现还是需要体会代码才能清晰.

AC代码:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
const int maxm=2*1000*1000+100;
int n,m;
int tot;
int head[maxn];
struct Edge
{
    int to,next,w;
}edges[maxm];
void add_edge(int u,int v,int w)
{
    edges[tot]=(Edge){v,head[u],w};
    head[u]=tot++;
    edges[tot]=(Edge){u,head[v],w};
    head[v]=tot++;
}

int pre[maxn],low[maxn];
int dfs_clock,point_num;
int ans;
void tarjan(int u,int E)
{
    low[u]=pre[u]=++dfs_clock;
    for(int e=head[u];e!=-1;e=edges[e].next)
    {
        int v=edges[e].to;
        if(e==(E^1)) continue;
        if(!pre[v])
        {
            tarjan(v,e);
            low[u]=min(low[u],low[v]);
            if(low[v]>pre[u])
                ans=min(ans,edges[e].w);
        }
        else low[u]=min(low[u],pre[v]);
    }
    point_num++;
}
int main()
{
    while(scanf("%d%d",&n,&m)==2&&n)
    {
        ans=1000000;
        dfs_clock=point_num=tot=0;
        memset(pre,0,sizeof(pre));
        memset(head,-1,sizeof(head));
        for(int i=0;i<m;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add_edge(u,v,w);
        }
        tarjan(1,-1);
        if(point_num<n) printf("0\n");          //图不连通,不用炸
        else if(ans==1000000) printf("-1\n");   //图中无桥
        else if(ans==0) printf("%d\n",1);       //桥上兵为0
        else printf("%d\n",ans);
    }
    return 0;
}