文章目录

• 题目
• 分析
• 代码

题目

[APIO 2013] 道路费用

分析

首先考虑暴力： 2 K 2^K 2K 枚举哪些边在最终的最小生成树里面，把和这些边冲突的边不要，做一遍最小生成树即可。选的边的权值肯定是与最小冲突边以及最小生成树形成的环中最大的，就能确定最终获利了。时间复杂度 O ( 2 K M log ⁡ M ) O(2^KM\log M) O(2KMlogM)。

事实上我们可以事先处理出冲突边，因为 边权互不相同，所以 最小 冲突边仅有 K K K 条。因此我们先把 K K K 条边连入并查集，做一遍最小生成树，得到的边一定是存在于暴力枚举中的每一个最小生成树中的。那么只需要考虑把 K K K 条边中的一些替换成他们对应的最小冲突边，就能确定这个最小生成树了。时间复杂度 O ( 2 K K 2 ) O(2^KK^2) O(2KK2)（瓶颈在计算环的最大值，需要暴力向上爬）。

代码

#include <bits/stdc++.h>

int Read() {
	int x = 0; bool f = false; char c = getchar();
	while (c < '0' || c > '9')
		f |= c == '-', c = getchar();
	while (c >= '0' && c <= '9')
		x = x * 10 + (c ^ 48), c = getchar();
	return f ? -x : x;
}

typedef long long LL;

const int MAXN = 100000;
const int MAXK = 20;
const int MAXM = 300000;
const int INF = 0x3f3f3f3f;

int N, M, K;
int C[MAXN + 5];
struct Edge {
	int u, v, w;
} E[MAXM + 5];
int U[MAXK + 5], V[MAXK + 5];

inline bool Comp(const Edge &i, const Edge &j) {
	return i.w < j.w;
}

struct DSU {
	int Par[MAXN + 5];

	void Init(const int &n) {
		for (int i = 1; i <= n; i++)
			Par[i] = i;
	}
	int Find(const int &u) {
		return Par[u] == u ? u : (Par[u] = Find(Par[u]));
	}
	bool Unite(const int &u, const int &v) {
		if (Find(u) != Find(v))
			return Par[Find(u)] = Find(v), true;
		return false;
	}
} A, B;

int Num[MAXN + 5], Cnt;
std::vector<Edge> Add;

struct GraphEdge {
	int v; GraphEdge *nxt;
} *Adj[MAXK + 5], G[MAXK * 2 + 5], *EdgeCnt;

int R;
int Fat[MAXK + 5], Dep[MAXK + 5];
LL Val[MAXK + 5], Siz[MAXK + 5]; int Min[MAXK + 5];

void AddEdge(const int &u, const int &v) {
	(++EdgeCnt)->v = v, EdgeCnt->nxt = Adj[u], Adj[u] = EdgeCnt;
	(++EdgeCnt)->v = u, EdgeCnt->nxt = Adj[v], Adj[v] = EdgeCnt;
}

void Dfs(const int &u, const int &f) {
	Siz[u] = Val[u], Dep[u] = Dep[Fat[u] = f] + 1;
	for (GraphEdge *i = Adj[u]; i; i = i->nxt)
		if (i->v != f) {
			Dfs(i->v, u);
			Siz[u] += Siz[i->v];
		}
}

int main() {
	N = Read(), M = Read(), K = Read();
	for (int i = 1; i <= M; i++)
		E[i].u = Read(), E[i].v = Read(), E[i].w = Read();
	for (int i = 1; i <= K; i++)
		U[i] = Read(), V[i] = Read();
	for (int i = 1; i <= N; i++)
		C[i] = Read();

	std::sort(E + 1, E + M + 1, Comp);
	A.Init(N), B.Init(N);
	for (int i = 1; i <= K; i++)
		A.Unite(U[i], V[i]);
	for (int i = 1; i <= M; i++)
		if(A.Unite(E[i].u, E[i].v))
			B.Unite(E[i].u, E[i].v);
	for (int i = 1; i <= N; i++)
		if (B.Find(i) == i)
			Num[i] = ++Cnt;
	for (int i = 1; i <= N; i++)
		Val[Num[B.Find(i)]] += C[i];
	R = Num[B.Find(1)];
	A = B;
	for (int i = 1; i <= M; i++)
		if (A.Unite(E[i].u, E[i].v))
			Add.push_back(E[i]);
	for (Edge &e: Add)
		e.u = Num[B.Find(e.u)], e.v = Num[B.Find(e.v)];
	for (int i = 1; i <= K; i++)
		U[i] = Num[B.Find(U[i])], V[i] = Num[B.Find(V[i])];

	LL Ans = 0;
	int lim = 1 << K;
	for (int s = 1; s < lim; s++) {
		EdgeCnt = G;
		for (int i = 1; i <= K + 1; i++)
			A.Par[i] = i, Adj[i] = NULL, Siz[i] = 0, Min[i] = INF;
		bool con = false;
		for (int i = 1; i <= K; i++)
			if ((s >> (i - 1)) & 1) {
				if (!A.Unite(U[i], V[i])) {
					con = true;
					break;
				}
				AddEdge(U[i], V[i]);
			}
		if (con) continue;
		for (Edge e: Add)
			if (A.Unite(e.u, e.v))
				AddEdge(e.u, e.v);
		Dfs(R, 0);
		for (Edge e: Add) {
			int u = e.u, v = e.v, w = e.w;
			while (u != v) {
				if (Dep[u] < Dep[v])
					std::swap(u, v);
				Min[u] = std::min(Min[u], w);
				u = Fat[u];
			}
		}
		LL tot = 0;
		for (int i = 1; i <= K; i++) {
			if ((s >> (i - 1)) & 1) {
				int u = U[i], v = V[i];
				if (Dep[u] < Dep[v])
					std::swap(u, v);
				tot += Siz[u] * Min[u];
			}
		}
		Ans = std::max(Ans, tot);
	}
	printf("%lld", Ans);
	return 0;
}