题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4738
题意：给定一个n个节点m条边的无向图（可能不连通、有重边），每条边有一个权值。判断其连通性，若双连通，输出-1；若非连通，输出0；否则，输出权值最小的桥的权值。
思路：进行双连通域分解，记下连通块的个数和所有桥的情况，对应输出结果即可。
注意对重边的处理。这里我按照上一道题学到的姿势如法炮制：先把所有边按“字典序”排序（u, v, w），这样重边聚集在一起了，然后扫描一遍，发现重边即在结构体Edge中打重边标记；由于重边一定不是桥，因此选哪个的权值实际上无所谓。
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 }
判桥用 edges[i].isBrg 或 belong[u] == belong[v]都可以，二者等价。
多组样例，我开始用第一种但忘记在addEdge中把isBrg清零了才会WA。
时间： 2025-01-13 04:53:35