HDU 2242 考研路茫茫——空调教室
思路：求边双连通分量。然后进行缩点，点权为双连通分支的点权之和，缩点完变成一棵树，然后在树上dfs一遍就能得出答案
代码：
#include#include #include #include #include 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 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;}