MYF

HDU 4738 Caocao's Bridges

Posted on | In | | Visitors

题目链接

HDU 4738

解题方法：找割桥

题目分析

题目大意

　　曹操在长江上建立了一些点，点之间有一些边连着。如果这些点构成的无向图变成了连通图，那么曹操就无敌了。刘备为了防止曹操变得无敌，就打算去摧毁连接曹操的点的桥。但是诸葛亮把所有炸弹都带走了，只留下一枚给刘备。所以刘备只能炸一条桥。

　　题目给出n，m。表示有n个点，m条桥。

　　接下来的m行每行给出a，b，c，表示a点和b点之间有一条桥，而且曹操派了c个人去守卫这条桥。

　　现在问刘备最少派多少人去炸桥。

　　如果无法使曹操的点成为多个连通图，则输出-1.

解析

典型的找割桥的问题，但是比较坑的是会有重边，我的处理方法是，如果这个桥之前出现过，就将这个桥上的人数赋值为INF，这样建图的时候就可以保证答案不会在这个有重边的桥上取，如果不是桥的话，反正也不会去判断要不要取，所以赋值为INF也无所谓了。有一个小trick，当桥上没有人的话，需要派一个兵去炸。如果本来就是多个连通块的话，则不需要派人去炸，因为曹操不可能无敌。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
//HDU 4738
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream>
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;
const int maxn=1000+10;
int n,m,ans;
int dfs_clock;
vector<int> G[maxn];
int pre[maxn],low[maxn];
int mp[maxn][maxn];
int dfs(int u,int fa = -1){
    int lowu = pre[u] = ++dfs_clock;
    for (int i=0; i<G[u].size(); i++) {
        int v = G[u][i];
        if (!pre[v]) {
            int lowv = dfs(v, u);
            lowu = min(lowu, lowv);
            if (lowv > pre[u]) {//Bridge
                ans = min(ans, mp[u][v]);
            }
        }
        else if (pre[v] < pre[u] && v!=fa)
            lowu = min(lowu, pre[v]);
    }
    return low[u] = lowu;
}
int main(){
    while (scanf("%d%d",&n,&m)!=EOF) {
        if (n==0) break;
        memset(mp, INF, sizeof(mp));
        memset(pre, 0, sizeof(pre));
        memset(low, 0, sizeof(low));
        ans = INF;
        for (int i=1; i<=n; i++) G[i].clear();
        while (m--) {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            if (mp[u][v]==INF) {
                G[u].push_back(v);
                G[v].push_back(u);
                mp[u][v] = mp[v][u] = w;
            }
            else{
                mp[u][v] = mp[v][u] = INF;
            }

        }
        dfs(1);
        bool flag = false;
        for (int i=1; i<=n; i++) {
            if (pre[i] == 0) {//没有连通上所有点
                flag = true;
                break;
            }
        }
        
        if (flag)
            cout<<0<<"\n"; //本身就不联通
        else if (ans == INF)
            cout<<"-1\n"; //没有桥
        else if(ans == 0)
            cout<<"1\n"; //有桥且桥上没人 派一个兵去炸
        else
            cout<<ans<<"\n"; //有桥有人，拼人头
    }
}