题解：P14401 [JOISC 2016] 电报 / Telegraph

这题，难在哪里？

思路

先考虑这个问题的弱化，如果不要求强连通，仅要求其构成若干个环，怎么做？

问题等价于修改几个位置，能够使得

A_i

两两不同，最小化其代价。我们不关心我们把

A_i

修改成了什么，我们只关心修改哪些，所以贪心思路很显然，对于多个相同

A

的位置

i

，选择保留

C_i

最大的那个位置，剩下的修改，你就做完了。

考虑这个问题本身，首先其肯定不弱于刚才的问题，所以我们可以把刚才的部分照搬。于是问题转化为我们剩下了一些图，我们的要求是花费最小的代价破掉里面剩下的环。

最简单的策略就是在每个环上都找到删除代价最小的一条边，但是这可能是错的，因为对于那些入度大于

1

的点，我们在前半段处理的时候就强制令其删掉了多余的边，如果我们选择删掉在环中的边，然后连上不在环中的一条边，代价可能更小。

所以，对于入度大于

1

的点，我们记录下连向他的边修改代价最大的一条，代价记为

M

，次大的一条，代价记为

M'

，那么我们可以通过一次

M-M'

代价的修改，破坏掉一个环。

然后我们按照上述策略破坏掉所有的环就做完了，时间复杂度线性。

注意 corner case，即刚开始整个图就是一个大环的情况，显然无需任何操作，代价为

0

。

代码

CPP

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const ll N=1e5+10;
const ll INF=2147483647;
ll a[N],V[N],ans,n,cnt[N];
ll maxx[N],semaxx[N],ned;
ll stk[N],top,kep[N];
ll vis[N];
bool flag;
void dfs(ll now,ll col){
	vis[now]=col;stk[++top]=now;
	if(vis[a[now]]!=0){
		if(vis[a[now]]!=col) return;
		flag=1;
		while(stk[top+1]!=a[now]){
			if(cnt[stk[top]]>1) ned=min(ned,maxx[stk[top]]-semaxx[stk[top]]);
			else ned=min(ned,maxx[stk[top]]);
			top--;
		}
	}
	else dfs(a[now],col);
}
ll clc;
void predfs(ll now){
	vis[now]=1;clc++;
	if(!vis[a[now]]) predfs(a[now]);
	if(a[now]==1) flag=1;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(ll i=1;i<=n;i++){
		cin>>a[i]>>V[i];
		cnt[a[i]]++;
		if(cnt[a[i]]==1) maxx[a[i]]=V[i],kep[a[i]]=i;
		else{
			if(cnt[a[i]]==2){
				semaxx[a[i]]=V[i];
				if(semaxx[a[i]]>maxx[a[i]]){
					swap(semaxx[a[i]],maxx[a[i]]);
					kep[a[i]]=i;
				}
			}
			else{
				if(V[i]>maxx[a[i]]){
					semaxx[a[i]]=maxx[a[i]];
					maxx[a[i]]=V[i];
					kep[a[i]]=i;
				}
				else if(V[i]>semaxx[a[i]]) semaxx[a[i]]=V[i];
			}
		}
		ans+=V[i];
	}
	flag=0;predfs(1);
	if(clc==n&&flag){
		cout<<"0";
		return 0;
	}
	for(ll i=1;i<=n;i++) vis[i]=0;
	for(ll i=1;i<=n;i++){
		if(!cnt[i]) continue;
		vis[kep[i]]=1;
		ans-=maxx[i];
	}
	for(ll i=1;i<=n;i++) vis[i]^=1;
	for(ll i=1;i<=n;i++){
		if(vis[i]!=0) continue;
		top=0;flag=0;ned=INF;
		dfs(i,i+1);
		if(flag) ans+=ned;
	}
	cout<<ans;
	return 0;
}

题解：P14401 [JOISC 2016] 电报 / Telegraph

文章操作

思路

代码

相关推荐

评论

题解：P14401 [JOISC 2016] 电报 / Telegraph