HDU 2242 考研路茫茫——空调教室(边双连通）

HDU 2242 考研路茫茫——空调教室

题目链接

思路：求边双连通分量。然后进行缩点，点权为双连通分支的点权之和，缩点完变成一棵树，然后在树上dfs一遍就能得出答案

代码：

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <vector>

using namespace std;

const int N = 10005;

const int M = 20005;

int n, m, val[N];

struct Edge {

	int u, v, id;

	bool iscut;

	Edge() {}

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

		this->u = u;

		this->v = v;

		this->id = id;

		this->iscut = false;

	}

} edge[M * 2], cut[M];

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

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

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

	next[en] = first[u];

	first[u] = en++;

}

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

void dfs_cut(int u, int fa) {

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

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

		int v = edge[i].v;

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

		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;

				cut[cutn++] = edge[i];

			}

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

	}

}

void find_cut() {

	dfs_clock = 0; cutn = 0;

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

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

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

}

void dfs_bcc(int u) {

	pre[u] = 1;

	bccno[u] = bccn;

	bccval[bccn] += val[u];

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

		if (edge[i].iscut) continue;

		int v = edge[i].v;

		if (pre[v]) continue;

		dfs_bcc(v);

	}

}

vector<int> bcc[N];

void find_bcc() {

	bccn = 0;

	memset(bccval, 0, sizeof(bccval));

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

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

		if (!pre[i]) {

			dfs_bcc(i);

			bccn++;

		}

	}

}

const int INF = 0x3f3f3f3f;

int ans, tot;

int gao(int u, int fa) {

	int sum = bccval[u];

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

		int v = bcc[u][i];

		if (v == fa) continue;

		int tmp = gao(v, u);

		sum += tmp;

		ans = min(ans, abs(tot - 2 * tmp));

	}

	return sum;

}

int main() {

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

		en = 0;

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

		tot = 0;

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

			scanf("%d", &val[i]);

			tot += val[i];

		}

		int u, v;

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

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

			add_edge(u, v, i);

			add_edge(v, u, i);

		}

		find_cut();

		find_bcc();

		if (cutn == 0) {

			printf("impossible\n");

			continue;

		}

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

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

			int u = bccno[cut[i].u];

			int v = bccno[cut[i].v];

			bcc[u].push_back(v);

			bcc[v].push_back(u);

		}

		ans = INF;

		gao(0, -1);

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

	}

	return 0;

}