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;  
}