题目大意

给你一个\(n\)个点的环，每条边有方向，改变第\(i\)条边的方向代价为\(w_i\)，问将其改为强连通图的最小代价。\(n\leqslant100\)

题解

求出把边全部改为顺时针和全部改为逆时针的代价，较少的输出即可

卡点

无

C++ Code：



#include <cstdio>

#include <iostream>

#include <algorithm>

const int maxn = 111;

int head[maxn], cnt;

struct Edge { int to, nxt; } e[maxn << 1];

void addedge(int a, int b) {

	e[++cnt] = (Edge) { b, head[a] }; head[a] = cnt;

	e[++cnt] = (Edge) { a, head[b] }; head[b] = cnt;

}

int n, dep[maxn], l[maxn], r[maxn], w[maxn], res1, res2;

void dfs(int u) {

	for (int i = head[u], v; i; i = e[i].nxt) {

		v = e[i].to;

		if (!dep[v]) dep[v] = dep[u] + 1, dfs(v);

	}

}

int main() {

	std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);

	std::cin >> n;

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

		std::cin >> l[i] >> r[i] >> w[i];

		addedge(l[i], r[i]);

	}

	dfs(dep[1] = 1);

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

		if (dep[r[i]] != dep[l[i]] % n + 1) res2 += w[i];

		else res1 += w[i];

	}

	std::cout << std::min(res1, res2) << '\n';

	return 0;

}

巴特西

[CF24A]Ring road(2019-11-15考试)

题目大意

题解

卡点

C++ Code：

最新文章

热门文章