杭二集训 电报

树和图中奇妙的贪心

Posted by yjjr's blog on January 6, 2018

标签:贪心,树形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;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr