ABC 256 E（图）

嘿嘿，我今天又来更一道E题！

E Takahashi's Anguish

题面

有n个人，每个人都要发一块糖，
但是他们之间有仇恨，第 $ i $ 个人仇恨第 $ X_i $ 个人。
如果第 $ X_i $ 个人发糖早于第 $ i $ 个人，那么第 $ i $ 个人将会有仇恨 $ C_i $ 点。
问怎样选择发糖的顺序，使得这些人的仇恨点数和最小。
你只需要输出最小仇恨点数和就行了。

思路

首先我们建图，对于每一个 $ i $，我们建一个 $ i \rightarrow X_i $ 的边（双向边，可以有重边），权值为 $ C_i $。
接着，我们找到图中的每一个环（详情见最后的 $ 0xFF $），计算这个环上最短的边，取所有环的总和。
实际写代码的时候，不需要记录权值，留着 $ C_i $ 即可。

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define maxn 200005

vector gg[maxn];
queue bfs_q;
int d[maxn];
long long c[maxn];

long long cycle_bfs(int x) {
	long long ans = 0x3f3f3f3f3f3f3f3f;
	bfs_q.push(x);
	while (bfs_q.size()) {
		int n = bfs_q.front();
		bfs_q.pop();
		ans = min(ans, c[n]);
		for (int adj_node : gg[n]) {
			d[adj_node]--;
			if (d[adj_node] == 1 && adj_node != x) {
				bfs_q.push(adj_node);
			}
		}
	}
	return ans;
}

int main() {
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		int x;
		scanf("%d", &x);
		gg[i].push_back(x - 1);
		gg[x - 1].push_back(i);
	}
	for (int i = 0; i < n; i++) {
		scanf("%lld", &c[i]);
	}
	for (int i = 0; i < n; i++) {
		d[i] = gg[i].size();
	}
	for (int i = 0; i < n; i++) {
		if (d[i] == 1) {
			bfs_q.push(i);
		}
	}
	while (bfs_q.size()) {
		int x = bfs_q.front();
		bfs_q.pop();
		for (int adj_node : gg[x]) {
			d[adj_node]--;
			if (d[adj_node] == 1) {
				bfs_q.push(adj_node);
			}
		}
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		if (d[i] == 2) {
			long long this_ans = cycle_bfs(i);
			ans += this_ans;
		}
	}
	printf("%lld", ans);
	return 0;
}

附 $ 0b11111111 $

我们先统计出每个点的度数。
然后从度数为一的开始BFS，遇到一个就把度数数组里讨厌的人度数减1。
如果他的度数为1了，那就把他压进队列。
之后再从度数为2的开始BFS找环。

题解

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

最大数maxnumber - 题解【树状数组】

标签