首页 > 代码库 > hdu 4738 无向图缩点断桥 // 细节坑题

hdu 4738 无向图缩点断桥 // 细节坑题

Caocao‘s Bridges

题意:给个无向图,求出边权最小的桥。

一看,直接缩点,若无桥,输出-1,有桥,遍历下边,更新最小。。分分钟搞定,以为IA的。。一交wa。。。

坑点:1:若原图不连通,则无须派人去!输出0!;

            2:若桥的权是0,则还有派一个人把炸弹拿去,输出1!

          3:有重边。(按多条边算)。

哎!记住这个教训!以后做题

 1:考虑边界或者特殊数据!(边权为0!n==1等)

 2:考虑原图连通性!(这次考虑了原图就强连通。。没有考虑根本不连通!)

3:重边。这题的重边是按重边算(不是一条),而我采用的数据结构和算法恰好回避了这个问题(我用链式前向星和无向图自创tarjan模板可以重边按多边算(重边的点必在一个BCC中),若要重边按一条算,则用链星和第二套记录父亲点法tarjan来)。

这题WA真正元凶:不可原谅自己!在用e[i][0]时候,竟然又犯低级错误!!!i用边啊!用什么点!!!

#include<iostream>
#include<stack>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxv=1005,maxe=1000*1003;
int nume=0;int head[maxv];int e[maxe][3];
void inline adde(int i,int j,int c)
{
    e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;
    e[nume++][2]=c;
    e[nume][0]=i;e[nume][1]=head[j];head[j]=nume;
    e[nume++][2]=c;
}
int dfn[maxv];int low[maxv];int vis[maxv];int ins[maxv]; stack<int>sta;
int bcc[maxv];int numb=0;int times=0; int vise[maxe];
int n,m;
void tarjan(int u)
{
    dfn[u]=low[u]=times++;
    ins[u]=1;
    sta.push(u);
    for(int i=head[u];i!=-1;i=e[i][1])
    {
        if(vise[i])continue;
        int v=e[i][0];
        if(!vis[v])
        {
            vis[v]=1;
            vise[i]=vise[i^1]=1;
            tarjan(v);
            if(low[v]<low[u])low[u]=low[v];
        }
        else if(ins[v]&&dfn[v]<low[u])
        {
            low[u]=dfn[v];
        }
    }
    if(low[u]==dfn[u])
    {
        numb++;
        int cur;
       do
        {
            cur=sta.top();
            sta.pop();
            ins[cur]=0;
            bcc[cur]=numb;
        }while(cur!=u);
    }
}
void solve()
{
    int marks=0;
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
           tarjan(i);
           marks++;
        }
    }
    if(marks>=2)       //坑1
    {
       printf("0\n");return ;
    }
    if(numb==1)               
    {
        printf("-1\n");return ;
    }
    int mins=inf;
    for(int i=1;i<=n;i++) 
      for(int j=head[i];j!=-1;j=e[j][1])
      {
          if(bcc[i]!=bcc[e[j][0]])             //e[j][0]竟然写成e[i][0]!!!sb!!
        {
            if(e[j][2]<mins)mins=e[j][2];
        }
      }
    if(mins==0)mins=1;    //坑2
   printf("%d\n",mins);
}
void read_build()
{
    int aa,bb,cc;
    for(int i=0;i<m;i++)
    {
        scanf("%d%d%d",&aa,&bb,&cc);
        adde(aa,bb,cc);
    }
}
void init()
{
    numb=times=nume=0;
    memset(vise,0,sizeof(vise));
    for(int i=0;i<maxv;i++)
      {
          head[i]=-1;ins[i]=dfn[i]=low[i]=bcc[i]=vis[i]=0;
      }
}
int main()
{
    while(~scanf("%d%d",&n,&m)&&(n||m))
    {
        init();
        read_build();
        solve();
    }
    return 0;
}