HDU4738[杭州网赛、判桥]

刚拿到这道题时挺有思路，无奈平日里只敲过找割顶的代码，判桥的代码当时自己也没仔细敲。

当时一把泪啊，忽然感觉自己的图论才只是刚搞了个起步啊。。

题目有神坑。就是先判是否连通，不连通直接输出0;

还有一个比较坑的是有重边的情况，那这样就有重边的两点之间就不可能存在桥。

再就是桥上无士兵把守也要派一个人去炸。

。。。

#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <vector>  
#include <algorithm>  
using namespace std;  
  
const int maxn = 1500;  
int dfs_clock, current_clock, ans, current_cc;  
int adj[maxn][maxn], iscut[maxn], vis[maxn], pre[maxn], low[maxn];  
vector<int> G[maxn];  
int n, m, a, b, c, INF = 10000000;  
  
void dfs(int u)  
{  
    vis[u] = 1;  
    //PREVISIT(u); 访问u之前的操作  
    for(int i = 0; i < G[u].size(); i++)  
    {  
        int v = G[u][i];  
        if(!vis[v]) dfs(v);  
    }  
    //POSTVISIT(u); 访问结点u之后的操作  
}  
  
void find_cc()  //给连通分量标号  
{  
    current_cc = 0;  
    memset(vis, 0, sizeof(vis));  
    for(int u = 1; u <= n; u++) if(!vis[u])  
    {  
        current_cc++;  
        dfs(u);  
    }  
}  
  
int dfs_bridge(int u,int fa) //u在dfs树中的父结点是fa  
{  
    int lowu = pre[u] = ++dfs_clock;  
    int child = 0;    //子结点数目  
    for(int i = 0; i < G[u].size(); i++)  
    {  
        int v = G[u][i];  
        if(!pre[v])   //没有访问过v  
        {  
            child++;  
            int lowv = dfs_bridge(v, u);  
            lowu = min(lowu, lowv);  
            if(lowv >= pre[u])  
            {  
                iscut[u] = true;   //割点判断  
                if(lowv > pre[u] && adj[u][v] != -2) //桥的判断可以相应灵活处理  
                   ans = min(ans, adj[u][v]);  
            }  
        }  
        else if(pre[v] < pre[u] && v != fa)  
            lowu = min(lowu, pre[v]);  //用反向边更新u的low函数  
    }  
    if(fa < 0 && child == 1)  
    {  
        // 但是不用加是否单独判桥的判断？  
        iscut[u] = 0;  //应该是避免单结点判桥、割顶的情况吧  
    }  
    low[u] = lowu;  
    return lowu;  
}  
  
void init()  
{  
    memset(pre, 0, sizeof(pre));  
    memset(iscut, 0, sizeof(iscut));  
    memset(adj, -1 ,sizeof(adj));  
    for(int i = 0; i <= n; i++)  
        G[i].clear();  
}  
  
int main()  
{  
    while(scanf("%d%d",&n, &m) != EOF)  
    {  
        if(!n && !m) break;  
        init();  
        while(m--)  
        {  
            scanf("%d%d%d", &a, &b, &c);  
            if(adj[a][b] == -1)  
            {  
                G[a].push_back(b);  
                G[b].push_back(a);  
                adj[a][b] = c;  
                adj[b][a] = c;  
            }  
            else // 两点之间有两条边肯定不可能是桥  
            {  
               adj[a][b] = -2;  
               adj[b][a] = -2;  
            }  
        }  
  
        ans = INF;  
        dfs(1);  find_cc();  
        //printf("~%d\n",current_cc);  
        if(current_cc >= 2) { printf("0\n"); continue;}  
        else dfs_bridge(1, -1);  
        if(ans == 0) printf("1\n");  
        else if(ans == INF ) printf("-1\n");  
        else printf("%d\n", ans);  
    }  
    return 0;  
}

补充：软件开发 , C++ ,