hdu 4612 Warm up(边-双连通+缩点+树的直径) - c++编程基础

TOP

hdu 4612 Warm up(边-双连通+缩点+树的直径)

2014-11-23 17:41:23 来源: 作者: 【大中小】浏览:12次

题意是给定一个无向图，求增加一条边后，桥的最少可能的条数。

先求出所有桥（即双连通分量），然后缩点得到一颗树。增加一条边使得桥的数量最小，显然是连接bcc树上直径的两端了。

这个题hdu又会爆栈。。。开个挂才能过。。。

#pragma comment(linker,"/STACK:102400000,102400000")
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define FF(i, a, b) for(int i=a; i=b; i--)
#define REP(i, n) for(int i=0; i G[maxn], g[maxn];
vector edges;

inline void init()
{
    REP(i, n) G[i].clear(); edges.clear();
}

void add(int u, int v)
{
    Edge e; e.to = v, e.flag = 0;
    edges.PB(e);
    e.to = u;
    edges.PB(e);
    int nc = edges.size();
    G[u].PB(nc-2);
    G[v].PB(nc-1);
}

int dfs(int u, int fa)
{
    int lowu = pre[u] = ++dfs_clock;
    int nc = G[u].size();
    REP(i, nc)
    {
        int v = edges[G[u][i]].to;
        if(!pre[v])
        {
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if(lowv > pre[u]) edges[G[u][i]].flag = 1, edges[G[u][i]^1].flag = 1;
        }
        else if(pre[v] < pre[u] && v != fa) lowu = min(lowu, pre[v]);
    }
    return low[u] = lowu;
}

void dfs1(int u)
{
    bccno[u] = bcc_cnt;
    int nc = G[u].size();
    REP(i, nc)
    {
        int v = edges[G[u][i]].to;
        if(!bccno[v] && edges[G[u][i]].flag != 1) dfs1(v);
    }
}

void find_bcc()
{
    CLR(pre, 0); CLR(bccno, 0);
    dfs_clock = bcc_cnt = 0;
    REP(i, n) if(!pre[i]) dfs(i, -1);
    REP(i, n) if(!bccno[i]) bcc_cnt++, dfs1(i);
}

int mm, end;

void find(int u, int fa, int d)
{
    int nc = g[u].size();
    if(nc == 1)
    {
        if(d > mm)
        {
            mm = d;
            end = u;
        }
    }
    REP(i, nc)
    {
        int v = g[u][i];
        if(v != fa) find(v, u, d+1);
    }
}

int main()
{
    while(scanf("%d%d", &n, &m), n+m)
    {
        init();
        REP(i, m)
        {
            scanf("%d%d", &u, &v); u--; v--;
            add(u, v);
        }
        find_bcc();
        if(bcc_cnt == 1)
        {
            puts("0");
            continue;
        }
        REP(i, n+1) g[i].clear();
        REP(u, n)
        {
            int nc = G[u].size();
            REP(i, nc)
            {
                int v = edges[G[u][i]].to;
                if(bccno[u] != bccno[v]) g[bccno[u]].PB(bccno[v]);
            }
        }
        mm = 0;
        find(1, -1, 0);
        find(end, -1, 0);
        printf("%d\n", bcc_cnt - mm - 1);
    }
    return 0;
}


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：poj 1260 Pearls 斜率优化dp	下一篇：Adb分析及获取root权限

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: