【HDU 4738 Caocao's Bridges】BCC 找桥

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <algorithm>
  4 #include <vector>
  5 #define CLEAR(A, X) memset(A, X, sizeof(A))
  6 #define REP(N) for(int i=0; i<(N); i++)
  7 #define REPE(N) for(int i=1; i<=(N); i++)
  8 #define FREAD(FN) freopen((FN), "r", stdin)
  9 #define pb(a) push_back(a)
 10 
 11 using namespace std;
 12 
 13 const int MAX_N = 1005;
 14 const int MAX_M = 2000005;
 15 const int INF = 10005;
 16 int n, m;
 17 
 18 struct Edge
 19 {
 20     int v, next;
 21     int w;
 22     bool isBrg;
 23     bool isDup;
 24 }edges[MAX_M];
 25 int numE;
 26 int head[MAX_N];
 27 int low[MAX_N], dfn[MAX_N], clock;
 28 int inStack[MAX_N], S[MAX_N], topS;
 29 int block, belong[MAX_N];
 30 int numBrg;
 31 int cnt;//连通块个数
 32 
 33 void init(){
 34     numE = 0;
 35     clock = block = topS = 0;
 36     numBrg = 0;
 37     CLEAR(low, 0);
 38     CLEAR(dfn, 0);
 39     CLEAR(head, -1);
 40     CLEAR(belong, 0);
 41     CLEAR(inStack, 0);
 42 }
 43 
 44 
 45 void addEdge(int u, int v, int w, bool isDup){
 46     edges[numE].v = v;
 47     edges[numE].w = w;
 48     edges[numE].isBrg = 0;
 49     edges[numE].isDup = isDup;
 50     edges[numE].next = head[u];
 51     head[u] = numE++;
 52 
 53     //反向边
 54     edges[numE].v = u;
 55     edges[numE].w = w;
 56     edges[numE].isBrg = 0; //这里之前忘清零了，一直WA。。。
 57     edges[numE].isDup = isDup;
 58     edges[numE].next = head[v];
 59     head[v] = numE++;
 60 }
 61 
 62 void bcc(int u, int p, int isDup){
 63     low[u] = dfn[u] = ++clock;
 64     S[topS++] = u;
 65     inStack[u] = 1;
 66     for(int i=head[u]; i != -1; i = edges[i].next){
 67         int v = edges[i].v;
 68         if(v == p && (!isDup)) continue;
 69         if(!dfn[v]){
 70             bcc(v, u, edges[i].isDup);
 71             low[u] = min(low[u], low[v]);
 72             if(low[v] > dfn[u]){//bridge
 73                 numBrg++;
 74                 edges[i].isBrg = 1;
 75                 edges[i^1].isBrg = 1;
 76             }
 77         }else if(inStack[v]){//backward
 78             low[u] = min(low[u], dfn[v]);
 79         }
 80     }
 81     if(low[u] == dfn[u]){//new bcc
 82         block++;
 83         int t;
 84         do{
 85             t = S[--topS];
 86             inStack[t] = 0;
 87             belong[t] = block;
 88         }while(t != u);
 89     }
 90 }
 91 
 92 struct Node
 93 {
 94     int u, v, w;
 95     Node(){}
 96     Node(int uu, int vv, int ww):u(uu), v(vv), w(ww){}
 97 }nodes[MAX_M];
 98 bool cmp(Node a, Node b){
 99     if(a.u == b.u){
100         if(a.v == b.v) return a.w < b.w;
101         return a.v < b.v;
102     }
103     return a.u < b.u;
104 }
105 bool same(Node a, Node b){
106     return a.u == b.u && a.v == b.v;
107 }
108 
109 int main()
110 {
111     FREAD("4738.txt");
112     while(~scanf("%d%d", &n, &m) && !(n==0 && m==0)){
113         init();
114         REP(m){
115             int u, v, w;
116             scanf("%d%d%d", &u, &v, &w);
117             if(u > v) swap(u, v);//保持顺序
118             nodes[i] = Node(u, v, w);
119         }
120         sort(nodes, nodes+m, cmp);
121         int cur = 0, i = 1;
122         int flagDup = 0;
123         while(cur < m){
124             while(i < m && same(nodes[cur], nodes[i])){
125                 flagDup = 1;
126                 i++;
127             }//重边一定不是桥，
128             if(flagDup) addEdge(nodes[cur].u, nodes[cur].v, nodes[cur].w, true);
129             else addEdge(nodes[cur].u, nodes[cur].v, nodes[cur].w, false);
130             flagDup = 0;
131             cur = i++;
132         }
133         cnt = 0;
134         REPE(n){
135             if(!dfn[i]){
136                 bcc(i, 0, 0);
137                 cnt++;
138             }
139         }
140         int ans = INF;
141         if(cnt > 1) ans = 0;//非连通
142         else if(cnt==1 && !numBrg) ans = -1;//边双连通
143         else{//有桥
144             // REPE(n){
145             //     for(int j=head[i]; j != -1; j = edges[j].next){
146             //         int v = edges[j].v;
147             //         if(belong[i] != belong[v])
148             //             ans = min(ans, edges[j].w);
149             //     }
150             // }
151             REPE(numE){
152                 if(edges[i].isBrg)
153                     ans = min(ans, edges[i].w);
154             }
155             if(ans == 0) ans = 1;//至少派一人
156         }
157         printf("%d\n", ans);
158     }
159     return 0;
160 }