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

· · 题解

这题，难在哪里？

思路

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

问题等价于修改几个位置，能够使得 A_i 两两不同，最小化其代价。我们不关心我们把 A_i 修改成了什么，我们只关心修改哪些，所以贪心思路很显然，对于多个相同 A 的位置 i，选择保留 C_i 最大的那个位置，剩下的修改，你就做完了。

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

最简单的策略就是在每个环上都找到删除代价最小的一条边，但是这可能是错的，因为对于那些入度大于 1 的点，我们在前半段处理的时候就强制令其删掉了多余的边，如果我们选择删掉在环中的边，然后连上不在环中的一条边，代价可能更小。

所以，对于入度大于 1 的点，我们记录下连向他的边修改代价最大的一条，代价记为 M，次大的一条，代价记为 M'，那么我们可以通过一次 M-M' 代价的修改，破坏掉一个环。

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

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

代码

:::success[代码]

#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;
}

:::