【HDU 4738 Caocao's Bridges】BCC 找桥

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4738

题意：给定一个n个节点m条边的无向图（可能不连通、有重边），每条边有一个权值。判断其连通性，若双连通，输出-1；若非连通，输出0；否则，输出权值最小的桥的权值。

思路：进行双连通域分解，记下连通块的个数和所有桥的情况，对应输出结果即可。

注意对重边的处理。这里我按照上一道题学到的姿势如法炮制：先把所有边按“字典序”排序（u, v, w），这样重边聚集在一起了，然后扫描一遍，发现重边即在结构体Edge中打重边标记；由于重边一定不是桥，因此选哪个的权值实际上无所谓。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #define CLEAR(A, X) memset(A, X, sizeof(A))

 #define REP(N) for(int i=0; i<(N); i++)

 #define REPE(N) for(int i=1; i<=(N); i++)

 #define FREAD(FN) freopen((FN), "r", stdin)

 #define pb(a) push_back(a)

 using namespace std;

 const int MAX_N = ;

 const int MAX_M = ;

 const int INF = ;

 int n, m;

 struct Edge

 {

     int v, next;

     int w;

     bool isBrg;

     bool isDup;

 }edges[MAX_M];

 int numE;

 int head[MAX_N];

 int low[MAX_N], dfn[MAX_N], clock;

 int inStack[MAX_N], S[MAX_N], topS;

 int block, belong[MAX_N];

 int numBrg;

 int cnt;//连通块个数

 void init(){

     numE = ;

     clock = block = topS = ;

     numBrg = ;

     CLEAR(low, );

     CLEAR(dfn, );

     CLEAR(head, -);

     CLEAR(belong, );

     CLEAR(inStack, );

 }

 void addEdge(int u, int v, int w, bool isDup){

     edges[numE].v = v;

     edges[numE].w = w;

     edges[numE].isBrg = ;

     edges[numE].isDup = isDup;

     edges[numE].next = head[u];

     head[u] = numE++;

     //反向边

     edges[numE].v = u;

     edges[numE].w = w;

     edges[numE].isBrg = ; //这里之前忘清零了，一直WA。。。

     edges[numE].isDup = isDup;

     edges[numE].next = head[v];

     head[v] = numE++;

 }

 void bcc(int u, int p, int isDup){

     low[u] = dfn[u] = ++clock;

     S[topS++] = u;

     inStack[u] = ;

     for(int i=head[u]; i != -; i = edges[i].next){

         int v = edges[i].v;

         if(v == p && (!isDup)) continue;

         if(!dfn[v]){

             bcc(v, u, edges[i].isDup);

             low[u] = min(low[u], low[v]);

             if(low[v] > dfn[u]){//bridge

                 numBrg++;

                 edges[i].isBrg = ;

                 edges[i^].isBrg = ;

             }

         }else if(inStack[v]){//backward

             low[u] = min(low[u], dfn[v]);

         }

     }

     if(low[u] == dfn[u]){//new bcc

         block++;

         int t;

         do{

             t = S[--topS];

             inStack[t] = ;

             belong[t] = block;

         }while(t != u);

     }

 }

 struct Node

 {

     int u, v, w;

     Node(){}

     Node(int uu, int vv, int ww):u(uu), v(vv), w(ww){}

 }nodes[MAX_M];

 bool cmp(Node a, Node b){

     if(a.u == b.u){

         if(a.v == b.v) return a.w < b.w;

         return a.v < b.v;

     }

     return a.u < b.u;

 }

 bool same(Node a, Node b){

     return a.u == b.u && a.v == b.v;

 }

 int main()

 {

     FREAD("4738.txt");

     while(~scanf("%d%d", &n, &m) && !(n== && m==)){

         init();

         REP(m){

             int u, v, w;

             scanf("%d%d%d", &u, &v, &w);

             if(u > v) swap(u, v);//保持顺序

             nodes[i] = Node(u, v, w);

         }

         sort(nodes, nodes+m, cmp);

         int cur = , i = ;

         int flagDup = ;

         while(cur < m){

             while(i < m && same(nodes[cur], nodes[i])){

                 flagDup = ;

                 i++;

             }//重边一定不是桥，

             if(flagDup) addEdge(nodes[cur].u, nodes[cur].v, nodes[cur].w, true);

             else addEdge(nodes[cur].u, nodes[cur].v, nodes[cur].w, false);

             flagDup = ;

             cur = i++;

         }

         cnt = ;

         REPE(n){

             if(!dfn[i]){

                 bcc(i, , );

                 cnt++;

             }

         }

         int ans = INF;

         if(cnt > ) ans = ;//非连通

         else if(cnt== && !numBrg) ans = -;//边双连通

         else{//有桥

             // REPE(n){

             //     for(int j=head[i]; j != -1; j = edges[j].next){

             //         int v = edges[j].v;

             //         if(belong[i] != belong[v])

             //             ans = min(ans, edges[j].w);

             //     }

             // }

             REPE(numE){

                 if(edges[i].isBrg)

                     ans = min(ans, edges[i].w);

             }

             if(ans == ) ans = ;//至少派一人

         }

         printf("%d\n", ans);

     }

     return ;

 }

判桥用 edges[i].isBrg 或 belong[u] == belong[v]都可以，二者等价。

多组样例，我开始用第一种但忘记在addEdge中把isBrg清零了才会WA。