HDU 4005 The war(雙連通好題）

HDU 4005 The war

題目鏈接

題意：給一個連通的無向圖，每條邊有一個炸掉的代價，現在要建一條邊（你不不知道的），然後你要求一個你需要的最少代價，保證不管他建在哪，你都能炸掉使得圖不連通

思路：炸肯定要炸橋，所以先雙連通縮點，得到一棵樹，樹邊是要炸的，那麼找一個最小值的邊，從該邊的兩點出發，走的路徑中，把兩條包含最小值的路徑，的兩點連邊，形成一個環，這個環就保證了最低代價在裡面，除了這個環以外的最小邊，就是答案，這樣的話，就利用一個dfs，搜到每個子樹的時候進行一個維護即可

代碼：

#include 
#include 
#include 
#include 
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 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;
}