JOISC 2016 Day3 电报

前置知识（伪）

  • 基环树
  • 基环外向树
  • 基环内向树

此题就是一棵基环外向树。
其实这些都没什么用，跟这题没啥关系

思路

考试的时候不会做，考完才发现自己就差那么一点点...
首先考虑这样一张图：

我们的目的是让整个图成为一个环，但是这显然不是一个环。考虑怎么让下面那一陀东西接到上面那个环里面。

如上图右边所示，给出了一种方法把下面那一堆东西接到环里面(\(A->C\)是环上的一条边，\(A,C\)都是环上的点)。发现其实就是对于所有不在环上的点(这里把\(A\)也将就算进来)的价值最大的那个点保留下来，其他边修改下就可以成环并且通过环上的一条边接入。然后我们先得到了一个显然错误的算法。

  • 对于每个点去找子结点的最大值
  • \(ans = \sum c_i - \sum mx_i\)

这个算法问题在于并不能保证选出的边可以成环，当\(A->C\)这条边的价值最大的时候，显然\(A\)点下方的点没有算进来，无法成环。所以这个时候我们还要记录一个不在环上的最大子结点值，记作\(v2\)，前面的记作\(v1\)，由于这个环是完整的，而在这个环上的与那些不在环上的点相接的点之间的边全部可以随便改变方向，所以只要枚举到环上任意一条边，把这条边拆掉就行了。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define R register
#define LL long long
const int N = 1e6 + 5;

inline int read() {
	char a = getchar(); int x = 0,f = 1;
	for(; a > '9' || a < '0'; a = getchar()) if(a == '-') f = -1;
	for(; a >= '0' && a <= '9' ;a = getchar()) x = x * 10 + a - '0';
	return x * f;
}

int n, a[N], vis[N];
LL Ans = 0, v1[N], v2[N], c[N];

int main() {
	freopen("1.in","r",stdin);
	//freopen(".out","w",stdout);
	n = read();
	for(R int i = 1; i <= n; i ++) a[i] = read(), c[i] = read();
	int flg = 0;
	for(R int i = 1; i <= n; i ++) {
		if(vis[i]) continue;
		int j = i;
		while(!vis[j]) vis[j] = i, j = a[j];
		if(vis[j] == i) { 
			int x = 0;
			while(vis[j] != -1) vis[j] = -1, j = a[j], x ++;
			if ( n == x ) flg = 1;
		}
	}
	if (flg) { putchar('0'); putchar('\n'); return 0; }
	for(R int i = 1; i <= n; i ++) Ans += c[i];
	for(R int i = 1; i <= n; i ++) {
		v1[a[i]] = max(v1[a[i]], c[i]);
		if(vis[i] != -1) {
			v2[a[i]] = max(v2[a[i]], c[i]);
		}
	}
	for(R int i = 1; i <= n; i ++) Ans -= v1[i];
	for(R int i = 1; i <= n; i ++) {
		if(vis[i] != -1) continue;
		LL mn = 1e18; int j = i;
		while(vis[j] == -1) {
			int t=mn;
			mn = min(mn, v1[j] - v2[j]);
			vis[j] = 0; j = a[j];
		}
		Ans += mn;
	}
	printf("%lld\n", Ans);
	return 0;	
}