【UOJ #108】【APIO 2013】TOLL

http://uoj.ac/problem/108

好神的一道题啊。

原图边权互不相同是重点！

如果有一个点集，有两组边集，要求这两组边集的并集的最小生成树，可以对两组边集分别求一下最小生成树构成新的两组边集，再合并两组新的边集。

还有，对于一个给定的最小生成树，要加入一条边，求加入一条边之后的最小生成树，那么就有这条边把原生成树上的一条边踢掉，或者这条边踢不动原生成树上的任何一条边（这条边加入后构成的环中的任意一条边的边权都小于这条边）。

这道题先考虑一个暴力的做法：先\(2^k\)枚举哪些新道路一定在最小生成树中，先在最小生成树中加入这些新道路，在这个基础上再加原图的边形成最小生成树，然后树的形态确定了，就要确定新道路的值了。对于原图中的边没能加入最小生成树的，肯定要想踢掉它连上后形成的环上的边，但环上原图中的边一定不会被踢掉，只可能踢掉环上的新道路。新道路为了防止自己被踢，就把自己的边权和这条想踢掉它的边的边权取min。

正解就是：改造原图！

先将所有新道路加入最小生成树，原图中最小生成树上没有通过新道路连通的点都缩成一个点（因为这些点之间的边不会对新道路的边权产生任何影响）。缩点之后的原图去掉新道路再求一遍最小生成树，设边集为\(M\)，在最外层\(2^k\)枚举哪些新道路一定在最小生成树中，然后拿\(M\)中的边继续加入，无法加入就用来更新新道路的权值。在这里用\(M\)中的边和用缩点后原图的边是等价的，因为\(M\)中的边能代表原图的连通性，而且原图中的边能加入最小生成树的边一定在\(M\)中（是\(M\)的子集），能更新新道路边权的边也一定能被\(M\)中的一条边代替。

时间复杂度\(O(m\log m+2^kk^2)\)。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = 100003;

const int M = 300003;

const int K = 23;

struct Enode {

	int u, v, e;

	bool operator < (const Enode &AA) const {

		return e < AA.e;

	}

} G[M], A[K], New[M], MN[K];

int p[N], Gtot = 0, n, m, k, fa[N], fa2[N], Atot = 0, Newtot = 0, MNtot = 0, tot = 0, remark[N];

ll sp[N];

int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}

int find2(int x) {return x == fa2[x] ? x : fa2[x] = find2(fa2[x]);}

ll sum[K];

bool used[K], mark[K];

struct node {int nxt, to, w;} E[K * K << 1];

int cnt, point[K], deep[K], fadis[K];

void ins(int u, int v, int w) {E[++cnt] = (node) {point[u], v, w}; point[u] = cnt;}

void dfs(int x) {

	sum[x] = sp[x];

	for (int i = point[x]; i; i = E[i].nxt)

		if (E[i].to != fa[x]) {

			fa[E[i].to] = x;

			fadis[E[i].to] = E[i].w;

			deep[E[i].to] = deep[x] + 1;

			if (E[i].w == 0x7fffffff) mark[E[i].to] = true;

			else mark[E[i].to] = false;

			dfs(E[i].to);

			sum[x] += sum[E[i].to];

		}

}

void minit(int u, int v, int e) {

	if (deep[u] < deep[v]) u ^= v ^= u ^= v;

	while (deep[u] > deep[v]) {

		if (mark[u] && fadis[u] > e)

			fadis[u] = e;

		u = fa[u];

	}

	if (u == v) return;

	while (u != v) {

		if (mark[u] && fadis[u] > e)

			fadis[u] = e;

		if (mark[v] && fadis[v] > e)

			fadis[v] = e;

		u = fa[u]; v = fa[v];

	}

}

int main() {

	scanf("%d%d%d", &n, &m, &k);

	int u, v, e, etot = 0;

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

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

		G[++Gtot] = (Enode) {u, v, e};

	}

	stable_sort(G + 1, G + Gtot + 1);

	for (int i = 1; i <= n; ++i) fa[i] = fa2[i] = i;

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

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

		A[++Atot] = (Enode) {u, v, 0};

		u = find(u); v = find(v);

		if (u != v) fa[u] = v, ++etot;

	}

	for (int i = 1; i <= n; ++i) scanf("%d", p + i);

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

		u = find(G[i].u); v = find(G[i].v);

		if (u != v) {

			++etot;

			fa[u] = v;

			u = find2(G[i].u); v = find2(G[i].v);

			if (u != v) fa2[u] = v;

			if (etot == n - 1) break;

		}

	}

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

		if (!remark[find2(i)])

			remark[fa2[i]] = ++tot;

		remark[i] = remark[fa2[i]];

	}

	for (int i = 1; i <= n; ++i) sp[remark[i]] += p[i];

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

		u = remark[G[i].u]; v = remark[G[i].v];

		if (u != v)

			New[++Newtot] = (Enode) {u, v, G[i].e};

	}

	stable_sort(New + 1, New + Newtot + 1);

	for (int i = 1; i <= k; ++i) A[i].u = remark[A[i].u], A[i].v = remark[A[i].v];

	etot = 0;

	for (int i = 1; i <= tot; ++i) fa[i] = i;

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

		u = find(New[i].u); v = find(New[i].v);

		if (u != v) {

			fa[u] = v;

			++etot;

			MN[++MNtot] = New[i];

			if (etot == tot - 1) break;

		}

	}

	int S = (1 << k); ll ans = 0;

	for (int s = 1; s < S; ++s) {

		for (int i = 1; i <= tot; ++i) fa[i] = i, point[i] = 0;

		cnt = etot = 0;

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

			if ((s >> i) & 1) {

				u = A[i + 1].u; v = A[i + 1].v;

				if (find(u) != find(v)) {

					fa[fa[u]] = fa[v];

					++etot;

					ins(u, v, 0x7fffffff);

					ins(v, u, 0x7fffffff);

				}

			}

		for (int i = 1; i <= MNtot; ++i) used[i] = false;

		if (etot < tot - 1) {

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

				u = find(MN[i].u); v = find(MN[i].v);

				if (u != v) {

					used[i] = true;

					++etot;

					fa[u] = v;

					ins(MN[i].u, MN[i].v, MN[i].e);

					ins(MN[i].v, MN[i].u, MN[i].e);

					if (etot == tot - 1) break;

				}

			}

		}

		fa[remark[1]] = 0; dfs(remark[1]);

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

			if (!used[i])

				minit(MN[i].u, MN[i].v, MN[i].e);

		ll ret = 0;

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

			if (mark[i])

				ret += sum[i] * fadis[i];

		if (ret > ans) ans = ret;

	}

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

	return 0;

}