标签：贪心，树形DP
题目
【题目背景】 某国由 n 座岛屿组成，每座岛上都有一台无线电接收机。第 i 座岛屿的无线电接 收机可以接收来自第 ai 座岛屿的信息。通过改变天线的方向，你可以改变第 i 座岛屿 能够收到的信息的来源。改变第 i 座岛屿的无线电接收机的方向（即改变某个 ai 的值） 所需要的代价为 ci。 岛屿之间可以通过无线电来直接或间接地通信，即如果第 i 座岛屿能够发送信息给 第 j 座岛屿，并且第 j 座岛屿能够发送信息给第 k 座岛屿，那么第 i 座岛屿就能够发 送信息给第 k 座岛屿。 【题目描述】 现在你希望用最小的代价使得任意两座岛屿之间能够相互发送信息。 【输入格式】 从文件 telegraph.in 中读入数据。 输入第一行包含一个正整数 n，表示岛屿的数量。 接下来 n 行，每行两个整数。第 i 行的两个整数为 ai,ci，含义如题述。 【输出格式】 输出到文件 telegraph.out 中。 输出一行一个整数，表示最小代价。 【样例 1 输入】 4 2 2 1 4 1 3 3 1 【样例 1 输出】 4 【样例 2 输入】 4 2 2 1 6 1 3 3 1 【样例 2 输出】 5 【样例 3 输入】 4 2 2 1 3 4 2 3 3 【样例 3 输出】 4 【样例 4 输入】 3 2 1 3 1 1 1 【样例 4 输出】 0
分析
很多dalao都写出来DP，然而我并不会qwq
1e5的范围，正解是贪心
可以将原图看成一个带有分支的树，树中包含多个环
那么树支部分就可以贪心选择最大的子节点
环部分可以传递最大的环中节点到相接的分支上
先将ans累和c[i]，然后减去每个树中最大的子节点
然后找出每个环中最小的节点加到答案上
注意：要特判原本就是一个环的情况！还好样例给出了，出题人良心
话说微软的3D画图还挺好用（雾）
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define newreg(x) for(int i=rlast[x];i;i=re[i].next)
#define reg(x) for(int i=last[x];i;i=e[i].next)
#define inf 1e9
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e6+6;
int a[maxn],vis[maxn]={0},n;
ll c[maxn],t1[maxn],t2[maxn],ans;
int main()
{
n=read();
rep(i,1,n)a[i]=read(),c[i]=read();
bool flag=0;
rep(i,1,n){
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)flag=true;
}
}
if(flag){cout<<0<<endl;return 0;}//特判原本就是一个环的情况
rep(i,1,n)ans+=c[i];
rep(i,1,n){
t1[a[i]]=max(t1[a[i]],c[i]);//找最大的子节点
if(vis[i]!=-1)t2[a[i]]=max(t2[a[i]],c[i]);
}
//rep(i,1,n)cout<<t1[i]<<' ';cout<<endl;
//rep(i,1,n)cout<<t2[i]<<' ';cout<<endl;
rep(i,1,n)ans-=t1[i];
rep(i,1,n){
if(vis[i]!=-1)continue;
ll mx=inf,j=i;
while(vis[j]==-1){
mx=min(mx,t1[j]-t2[j]);
vis[j]=0;
j=a[j];
}
ans+=mx;
}
cout<<ans<<endl;
return 0;
}
