HDU 4005 The war

pid=4005" target="_blank" style="">题目链接

题意：给一个连通的无向图。每条边有一个炸掉的代价。如今要建一条边（你不不知道的），然后你要求一个你须要的最少代价，保证无论他建在哪，你都能炸掉使得图不连通

思路：炸肯定要炸桥，所以先双连通缩点，得到一棵树，树边是要炸的，那么找一个最小值的边。从该边的两点出发。走的路径中，把两条包括最小值的路径。的两点连边。形成一个环。这个环就保证了最低代价在里面。除了这个环以外的最小边。就是答案，这种话，就利用一个dfs，搜到每一个子树的时候进行一个维护就可以

代码：

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int N = 10005;

const int M = 200005;

int n, m;

struct Edge {

	int u, v, val, id;

	bool iscut;

	Edge() {}

	Edge(int u, int v, int val, int id) {

		this->u = u;

		this->v = v;

		this->val = val;

		this->id = id;

		this->iscut = false;

	}

} edge[M];

int en, first[N], next[M];

void init() {

	en = 0;

	memset(first, -1, sizeof(first));

}

void add_edge(int u, int v, int val, int id) {

	edge[en] = Edge(u, v, val, id);

	next[en] = first[u];

	first[u] = en++;

}

int pre[N], dfn[N], dfs_clock, bccn, bccno[N];

vector<Edge> bcc[N];

void dfs_cut(int u, int id) {

	pre[u] = dfn[u] = ++dfs_clock;

	for (int i = first[u]; i + 1; i = next[i]) {

		if (edge[i].id == id) continue;

		int v = edge[i].v;

		if (!pre[v]) {

			dfs_cut(v, edge[i].id);

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

			if (dfn[v] > pre[u])

				edge[i].iscut = edge[i^1].iscut = true;

		} else dfn[u] = min(dfn[u], pre[v]);

	}

}

void find_cut() {

	dfs_clock = 0;

	memset(pre, 0, sizeof(pre));

	for (int i = 1; i <= n; i++)

		if (!pre[i]) dfs_cut(i, -1);

}

void dfs_bcc(int u) {

	bccno[u] = bccn;

	for (int i = first[u]; i + 1; i = next[i]) {

		if (edge[i].iscut) continue;

		int v = edge[i].v;

		if (bccno[v]) continue;

		dfs_bcc(v);

	}

}

const int INF = 0x3f3f3f3f;

Edge Mine;

void find_bcc() {

	bccn = 0;

	memset(bccno, 0, sizeof(bccno));

	for (int i = 1; i <= n; i++) {

		if (!bccno[i]) {

			bccn++;

			dfs_bcc(i);

		}

	}

	for (int i = 1; i <= bccn; i++) bcc[i].clear();

	Mine.val = INF;

	for (int i = 0; i < en; i++) {

		if (!edge[i].iscut) continue;

		if (Mine.val > edge[i].val)

			Mine = edge[i];

		int u = bccno[edge[i].u], v = bccno[edge[i].v], w = edge[i].val;

		bcc[u].push_back(Edge(u, v, w, 0));

	}

}

int ans;

int dfs(int u, int f) {

	int Min1 = INF, Min2 = INF;

	for (int i = 0; i < bcc[u].size(); i++) {

		int v = bcc[u][i].v;

		if (v == f) continue;

		Min2 = min(min(dfs(v, u), bcc[u][i].val), Min2);

		if (Min2 < Min1) swap(Min1, Min2);

	}

	ans = min(ans, Min2);

	return Min1;

}

int main() {

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

		init();

		int u, v, w;

		for (int i = 0; i < m; i++) {

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

			if (u > n || v > n) continue;

			add_edge(u, v, w, i);

			add_edge(v, u, w, i);

		}

		find_cut();

		find_bcc();

		if (bccn == 1) {

			printf("-1\n");

			continue;

		}

		ans = INF;

		u = bccno[Mine.u]; v = bccno[Mine.v];

		dfs(u, v);

		dfs(v, u);

		if (ans == INF) ans = -1;

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

	}

	return 0;

}