2013 ACM/ICPC Asia Regional Hangzhou Online–1001

hdoj4738 Caocao’s Bridges
注意点:如果原图不连通,那么输出0,如果原图中权最小的桥的权是0,那么要输出1.

#include <stdio.h>
#include <string.h>
#define inf 0x3f3f3f3f
const int maxn=1000+10;
const int maxe=4000000+10;
typedef struct EdgeA{
    int w;
    int from;
    int to;
    int next;
}Edge;
Edge edge[maxe];
int head[maxn];
int dfn[maxn],low[maxn],belong[maxn];
int id,dcc,top,n,m;
int s[maxn];
Edge bridge[maxe];  //桥边的集合,
int cnt,bcnt;       //从0开始
void add(int u,int v,int w)
{
    edge[cnt].w=w;edge[cnt].from=u;edge[cnt].to=v;edge[cnt].next=head[u];
    head[u]=cnt++;
    return;
}
void dfs(int cur,int fa)
{
    dfn[cur]=low[cur]=++id;
    s[++top]=cur;
    bool flag=1;
    for(int i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==fa && flag) {flag=0;continue;}//处理反向边
        if(!dfn[v])
        {
            dfs(v,cur);
            if(low[cur]>low[v])
                low[cur]=low[v];
            else if(low[v]>dfn[cur])
            {
                bridge[bcnt].w=edge[i].w;
                bridge[bcnt].from=cur;   //存的桥是原图中的标号
                bridge[bcnt].to=v;
                bcnt++;
                dcc++;
                while(s[top]!=v)
                {
                    belong[s[top]]=dcc;
                    top--;
                }
                belong[s[top]]=dcc;top--;
            }
        }
        else if(low[cur]>dfn[v])
            low[cur]=dfn[v];
    }
    return;
}
void tarjan()
{
    id=top=dcc=bcnt=0;
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i])
        {
            dfs(i,-1);
            dcc++;
            while(top!=0)
            {
                belong[s[top]]=dcc;
                top--;
            }
        }
    }
    return;
}
bool visit[maxn];
void dfs2(int cur)
{
    visit[cur]=1;
    int i;
    for(i=head[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(visit[v]) continue;
        dfs2(v);
    }
    return;
}
bool connect()
{
    memset(visit,0,sizeof(visit));
    dfs2(1);
    for(int i=1;i<=n;i++)
        if(!visit[i]) {return 0;}
    return 1;
}
int main()
{
    int i,j;
    int u,v,w;
    while(scanf("%d%d",&n,&m)!=EOF && !(n==0 && m==0))
    {
        cnt=0;memset(head,-1,sizeof(head));
        int mind=inf;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);add(v,u,w);
            if(w<mind) mind=w;
        }
        tarjan();
        if(!connect()) {printf("0\n");continue;}
        if(dcc==1) printf("-1\n");
        else
        {
            int ans=inf;
            for(i=0;i<=bcnt-1;i++)
                if(bridge[i].w<ans) ans=bridge[i].w;
            if(ans==0) printf("1\n");
            else printf("%d\n",ans);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>