oj.uz

Submission #1102189

# Submission time Handle Problem Language Result Execution time Memory
1102189 2024-10-17T15:57:16 Z SP_Caramen Toll (APIO13_toll) C++14
100 / 100
 1795 ms 12284 KB 
#include <bits/stdc++.h>
#define long long long

using namespace std;

struct union_find {
	vector<int> s, p;

	union_find(int n = 0) : s(n, 1), p(n) {
		iota(p.begin(), p.end(), 0);
	}

	int find(int u) {
		if (p[u] != u) {
			p[u] = find(p[u]);
		}
		return p[u];
	}

	bool merge(int u, int v) {
		u = find(u);
		v = find(v);
		if (u == v) {
			return false;
		}
		if (s[u] < s[v]) {
			swap(u, v);
		}
		p[v] = u;
		s[u] = s[u] + s[v];
		return true;
	}

	bool same(int u, int v) {
		return find(u) == find(v);
	}

	int size(int u) {
		u = find(u);
		return s[u];
	}
};

/*
思维不难，但是一定一定要思路清晰。

1. 看到 k <= 20，想一想 bitmasks，如果想到了，不难想出一种简单的暴力：
我们枚举每一条需要选的边，然后强制把它加到树上（当然，如果出现环直接 pass）
再跑最小生成树，用边去限定我们那些没有确定边权的边（用了一个经典的结论），
时间复杂度为 2^k * mlogn，可以拿到约 56 分。

2. 我们发现，这整个过程中，总有一些边会加入到最小生成树，这也很好理解。
我们一共就 k 条可以选择的边，这些边能连起来的连通块就 k + 1 个，而图
一共有 n 个连通块，很显然一定是会有很多很多边需要连起来的。所以，我们
直接将所有 k 条边加入，然后再跑一边最小生成树，这个时候选择的边是一定
会一直选下去的。

3. 很自然的，我们缩一下点（这个使用并查集可以维护），我们现在就剩下了 k + 1
个点，再把剩余的那些原边跑一边最小生成树，这样子，我们就确保了多余的边只有
k 条，再算上原来的 k 条边，一共是 k * 2 条，瞎搞都可以。
*/

const int N = (int) 1E5;
const int M = (int) 3E5;
const int K = 20;
const int A = numeric_limits<int>::max();

int n, m, k;

bool t1[M];
array<int, 3> e1[M];
array<int, 2> e2[K];
array<int, 3> e3[K];
vector<int> e4[K + 1];

int a[N];
long e[K + 1];

void Kruskal1() {
	union_find s(n);
	for (int i = 0; i < k; i++) {
		int u = e2[i][0], v = e2[i][1];
		s.merge(u, v);
	}
	for (int i = 0; i < m; i++) {
		int u = e1[i][1], v = e1[i][2];
		t1[i] = s.merge(u, v);
	}
}

int root;

void Kruskal2() {
	union_find s1(n);
	for (int i = 0; i < m; i++) {
		int u = e1[i][1], v = e1[i][2];
		if (t1[i] == true) {
			s1.merge(u, v);
		}
	}
	int c = 0;
	vector<int> p(n, -1);
	for (int i = 0; i < n; i++) {
		if (s1.find(i) == i) {
			p[i] = c;
			c = c + 1;
		}
	}
	for (int i = 0; i < k; i++) {
		int u = e2[i][0], v = e2[i][1];
		u = p[s1.find(u)];
		v = p[s1.find(v)];
		e2[i] = {u, v};
	}
	int t = 0;
	union_find s2(k + 1);
	for (int i = 0; i < m; i++) {
		int u = e1[i][1], v = e1[i][2], w = e1[i][0];
		if (t1[i] == false) {
			int x = p[s1.find(u)];
			int y = p[s1.find(v)];
			if (s2.merge(x, y)) {
				e3[t] = {w, x, y};
				t = t + 1;
			}
		}
	}
	assert(t + 1 == c);
	for (int i = 0; i < n; i++) {
		int u = p[s1.find(i)];
		e[u] = e[u] + a[i];
	}
	root = p[s1.find(0)];
}

int p[K + 1], d[K + 1];
int g[K + 1];
long t[K + 1];

void DFS(int u) {
	t[u] = e[u];
	for (auto v : e4[u]) {
		if (v != p[u]) {
			p[v] = u;
			d[v] = d[u] + 1;
			DFS(v);
			t[u] = t[u] + t[v];
		}
	}
}

void check(int u, int v, int w) {
	while (u != v) {
		if (d[u] > d[v]) {
			swap(u, v);
		}
		g[v] = min(g[v], w);
		v = p[v];
	}
}

void solve() {
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		u = u - 1, v = v - 1;
		e1[i] = {w, u, v};
	}
	for (int i = 0; i < k; i++) {
		int u, v;
		cin >> u >> v;
		u = u - 1, v = v - 1;
		e2[i] = {u, v};
	}
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	sort(e1, e1 + m);
	Kruskal1();
	Kruskal2();

	// for (int i = 0; i < k; i++) {
	// 	cout << e2[i][0] << " " << e2[i][1] << "\n";
	// }
	// for (int i = 0; i < k; i++) {
	// 	cout << e3[i][1] << " " << e3[i][2] << " " << e3[i][0] << "\n";
	// }
	// return;

	long c = 0;
	for (int S = 0; S < (1 << k); S++) {
		union_find s(k + 1);
		bool f = true;
		for (int i = 0; i < k; i++) {
			if (S >> i & 1) {
				int u = e2[i][0], v = e2[i][1];
				if (not s.merge(u, v)) {
					f = false;
					break;
				}
			}
		}
		if (not f) {
			continue;
		}

		vector<bool> t3(k);
		for (int i = 0; i < k; i++) {
			int u = e3[i][1], v = e3[i][2];
			t3[i] = s.merge(u, v);
		}

		for (int i = 0; i < k + 1; i++) {
			e4[i] = vector<int>();
		}
		for (int i = 0; i < k; i++) {
			if (S >> i & 1) {
				int u = e2[i][0], v = e2[i][1];
				e4[u].push_back(v);
				e4[v].push_back(u);
			}
		}
		for (int i = 0; i < k; i++) {
			if (t3[i] == true) {
				int u = e3[i][1], v = e3[i][2];
				e4[u].push_back(v);
				e4[v].push_back(u);
			}
		}

		p[root] = -1;
		d[root] = 0;
		DFS(root);
		// g[i] 表示节点 i 到节点 i 的父节点的边权最大是多少，初始的，为 MAX 即可
		fill(g, g + k + 1, A);
		for (int i = 0; i < k; i++) {
			if (t3[i] == false) {
				int u = e3[i][1], v = e3[i][2], w = e3[i][0];
				check(u, v, w);
			}
		}

		long b = 0;
		for (int i = 0; i < k; i++) {
			if (S >> i & 1) {
				int u = e2[i][0], v = e2[i][1];
				int x = d[u] > d[v] ? u : v;
				b = b + t[x] * g[x];
			}
		}

		c = max(c, b);
	}
	cout << c << "\n";
}

int32_t main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	t = 1;
	for (int i = 0; i < t; i++) {
		solve();
	}
	return 0;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 2 ms 2520 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 2 ms 2520 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 4 ms 2388 KB Output is correct
6 Correct 3 ms 2388 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 2 ms 2520 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 4 ms 2388 KB Output is correct
6 Correct 3 ms 2388 KB Output is correct
7 Correct 129 ms 12212 KB Output is correct
8 Correct 139 ms 12252 KB Output is correct
9 Correct 135 ms 12212 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2388 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 2 ms 2520 KB Output is correct
4 Correct 2 ms 2388 KB Output is correct
5 Correct 4 ms 2388 KB Output is correct
6 Correct 3 ms 2388 KB Output is correct
7 Correct 129 ms 12212 KB Output is correct
8 Correct 139 ms 12252 KB Output is correct
9 Correct 135 ms 12212 KB Output is correct
10 Correct 1296 ms 12280 KB Output is correct
11 Correct 1795 ms 12284 KB Output is correct
12 Correct 1757 ms 12284 KB Output is correct