求一下权值最小的桥。
第一坑：如果图不连通，不用派人去炸桥，直接输出0
第二坑：可能会有重边
第三坑：如果桥上没有士兵守着，那至少要派一个人去炸桥。
#include<cstdio> #include<cstring> #include<cmath> #include<vector> #include<algorithm> using namespace std; const int maxn = 1000 + 10; //结点数量 const int Maxn = 2 * 1000 * 1000 + 10; //边的数量 int low[maxn]; int dfn[maxn]; int U[Maxn], V[Maxn], W[Maxn];//存初始边 int flag[Maxn];//判断第i条边是不是割边 int Father[maxn]; struct Edge { int from, to, id, ans;//ans为1，表示这条边是割边 } edge[Maxn]; vector<int>G[maxn];//邻接表 int N, M;//N个结点，M条边 int tmpdfn;//时间戳 int tot; int Start, End; void init() { for (int i = 0; i < maxn; i++) G[i].clear(); for (int i = 0; i < maxn; i++) Father[i] = i; memset(low, 0, sizeof(low)); memset(dfn, 0, sizeof(dfn)); memset(flag, 0, sizeof(flag)); low[1] = dfn[1] = 1; tmpdfn = 0; tot = 0; } void AddEdge(int u, int v) { edge[tot].from = u; edge[tot].to = v; edge[tot].id = tot; edge[tot].ans = 0; G[u].push_back(tot); tot++; edge[tot].from = v; edge[tot].to = u; edge[tot].id = tot; edge[tot].ans = 0; G[v].push_back(tot); tot++; } int Tarjan(int u, int id) { tmpdfn++; int lowu = dfn[u] = tmpdfn; for (int i = 0; i<G[u].size(); i++) { int B = G[u][i]; if (!dfn[edge[B].to]) { int lowv = Tarjan(edge[B].to, edge[B].id); lowu = min(lowu, lowv); if (lowv >= dfn[u]) { if (lowv>dfn[u]) edge[B].ans = 1; } } else if (dfn[edge[B].to]) { if (edge[B].id / 2 == id / 2) continue; lowu = min(lowu, dfn[edge[B].to]); } } low[u] = lowu; return lowu; } void Display_Cutting_edge() { for (int i = 0; i<2 * M; i++) if (edge[i].ans) flag[edge[i].id / 2] = 1; } int Find(int x) { if (x != Father[x]) Father[x] = Find(Father[x]); return Father[x]; } int main() { while (~scanf("%d%d", &N, &M)) { if (!N&&!M) break; int JIHE = N; init(); for (int i = 0; i < M; i++) { scanf("%d%d%d", &U[i], &V[i], &W[i]); int fu = Find(U[i]); int fv = Find(V[i]); if (fu != fv) Father[fu] = fv, JIHE--; AddEdge(U[i], V[i]); } if (JIHE != 1) { printf("%d ", 0); continue; } Start = 1; End = N; Tarjan(1, -1); Display_Cutting_edge(); int Ans = 0x7FFFFFFF; for (int i = 0; i < M; i++) if (flag[i] && W[i] < Ans) Ans = W[i]; if (Ans == 0x7FFFFFFF) printf("-1 "); else if (Ans == 0) printf("%d ", 1); else printf("%d ", Ans); } return 0; }