目錄

樹的直徑

題目：樹的直徑?（兩種解法）

做法一：?

?做法二：

樹的重心：

題目： 會議

?思路：

題目：醫(yī)院設置?

思路：

????????

????????

樹的直徑

定義：樹中距離最遠的兩個點之間的距離被稱為樹的直徑。

一共有兩種做法，先記結(jié)論，再給證明！?

做法一：

（1）任取一點作為起點x，找到距離該點最遠的一個點y；

（2）再找到距離y最遠的一點z，那么y、z之間的路徑就是一條直徑。

做法二：

（1）距離直徑上的一個點最遠的點和次遠的點一定是直徑的兩個頂點，所以我們只要能找到距離每一個點的最遠距離和次遠距離就能找到樹的直徑了。

做法一證明：核心是證明y一定是直徑的一個端點。

使用反證法證明，假設xy是直徑(x,y為直徑上點)，uv為非直徑(u,v為非直徑上點)。存在如下兩種情況。

• 第一種情況是兩者相交，故意假設v是距離u最遠的點，有以下推論：

  ua+av>ua+ay? ??=>? ? av>ay? ??=>? ? ?av+ax>ay+ax=xy

  假設不成立，因v可以代表任意一個不是直徑上的點，故距離u最遠的點一定是直徑上的點！

• ?第二種情況是兩者不相交，故意假設v是距離u最遠的點，有以下推論：

  ua+av>ua+ab+by? ??=>? ? av?>?ab+by? ??=>? ? av+ab+bx>ab+by+ab+bx=2*ab+xy

  假設不成立，因v可以代表任意一個不是直徑上的點，故距離u最遠的點一定是直徑上的點！

做法二證明：

前半句話不用……就不證明了吧，后半句“?只要能找到距離每一個點的最遠距離和次遠距離就能找到樹的直徑了?！?意思就是把任意兩點間的最長距離在某一點處砍成兩半，當然有距離此點的最長距離和次長距離就是兩頭頂點間的最長距離，那么對所有點統(tǒng)計一下自然就找到直徑長度了。

?????????

題目：樹的直徑?（兩種解法）

spfa，dijkstra多用于跑有環(huán)的圖，DAG圖求最長距離直接dfs_dp就行！

做法一：?

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int tot,n,d[N],head[N];//d[i]表示到i點的距離
struct node{int to,w,nxt;}e[N*2];
void add(int u,int v,int w){e[++tot]=(node){v,w,head[u]};head[u]=tot;}

void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to,w=e[i].w;
		if(v==fa)continue;
		d[v]=d[u]+w;//先更新再遞歸，因為d表示到u點的距離
		dfs(v,u);
	}
}
int main(){
	cin>>n;int u,v,w;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v>>w;add(u,v,w);add(v,u,w);
	}
	dfs(1,0);//從任意點找最遠距離的點
	int ans=-1;
	for(int i=1;i<=n;i++)
		if(d[i]>ans)ans=d[i],v=i;
	memset(d,0,sizeof(d));
	dfs(v,0);//此點必定在直徑上，再跑一遍就完了
	for(int i=1;i<=n;i++)
		if(d[i]>ans)ans=d[i];
	cout<<ans;
}

?做法二：

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int ans=-1,tot,n,head[N];//d[i]表示到i點的距離
struct node{int to,w,nxt;}e[N*2];
void add(int u,int v,int w){e[++tot]=(node){v,w,head[u]};head[u]=tot;}

int dfs(int u,int fa){
	int d1=0,d2=0;//d1是最長距離，d2是次長距離
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to,w=e[i].w;
		if(v==fa)continue;
		int d3=dfs(v,u)+w;//先更新距離
		if(d3>=d1) d2=d1,d1=d3;//如果是更長距離，最長和次長都更新
		else if(d3>d2)d2=d3;//如果僅比次長距離大，就僅更新次長距離
	}
	ans=max(ans,d1+d2);//最長距離加次長距離就是總長度
	return d1;//返回最長距離
}
int main(){
	cin>>n;int u,v,w;
	for(int i=1;i<=n-1;i++){
		cin>>u>>v>>w;add(u,v,w);add(v,u,w);
	}
	dfs(1,0);//從任意點開始
	cout<<ans;
	
}

?????????

????????

樹的重心：

題目： 會議

?????????

?思路：

首先，閱讀題目可以看出來，這道題目實際上就是求樹的重心。

樹的重心：

定義：找到一個點，其所有的子樹中最大的子樹節(jié)點數(shù)最少，那么這個點就是這棵樹的重心，刪去重心后，達到的效果是生成的多棵樹盡可能平衡。

舉個例子：

我們不妨設置d[i]表示以此點為根的所有點總距離和，cnt[i]表示以此為根的節(jié)點數(shù)

我們首先知道d[1]=16,cnt[1]=10我們來看d[2]應該怎么求,我們發(fā)現(xiàn)相對于d[1]來說，如果設2為最佳點,2,5,6其距離-1，剩下的1,4,3,7,8,9,10到其距離+1。

故：d[2]=d[1] - 3 + 7 =20

其中3是子根2對應的節(jié)點數(shù)cnt[2]，7是1為子根對應的節(jié)點數(shù)cnt[1]-cnt[2]

得：d[i]=d[fa]-cnt[i]+(cnt[1]-cnt[i])

那么只需要先dfs求出來d[1]和每個點的cnt[i]。然后就可以進行dp最終求出所有點的d[i]。

#include <bits/stdc++.h>
using namespace std;
const int N=50005;
int minn=0x3f3f3f3f,ans,n,d[N],cnt[N];
vector<int>ve[N];
void dfs(int u,int fa,int len){//一定別走fa回去
	cnt[u]++;//先加上自己
	for(int i=0;i<ve[u].size();i++){
		int v=ve[u][i];
		if(v==fa)continue;
		dfs(v,u,len+1);//先求孩子的cnt，之后求自己cnt
		cnt[u]+=cnt[v];
	}
	d[1]+=len;//最后求d[1]
}
void dp(int u,int fa){
	for(int i=0;i<ve[u].size();i++){
		int v=ve[u][i];
		if(v==fa)continue;
		d[v]=d[u]-2*cnt[v]+cnt[1];
		dp(v,u);//這里對自己進行轉(zhuǎn)移更新，再對孩子的更新
	}
}
int main(){
	cin>>n;int a,b;
	for(int i=1;i<n;i++){
		cin>>a>>b;
		ve[a].push_back(b);
		ve[b].push_back(a);
	}
	dfs(1,0,0);
	dp(1,0);
	for(int i=1;i<=n;i++){
		if(d[i]<minn)
			minn=d[i],ans=i;
	}
	cout<<ans<<" "<<minn;
}

上面我打注釋的地方一定要理解?

????????

????????

題目：醫(yī)院設置?

思路：

還是一道求樹的重心題。不過是每個點都有一個權(quán)值。那么把權(quán)值當成“另一個世界的節(jié)點數(shù)”就好了。然后不斷求cnt，之后dp就行。?

#include <bits/stdc++.h>
using namespace std;
const int N=500;
int ans=0x3f3f3f3f,n,d[N],cnt[N],w[N];
vector<int>ve[N];
void dfs(int u,int fa,int len){
	cnt[u]=w[u];//這里還是先加自己
	for(int i=0;i<ve[u].size();i++){
		int v=ve[u][i];
		if(v==fa)continue;
		dfs(v,u,len+1);
		cnt[u]+=cnt[v];
	}
	d[1]+=len*w[u];//更新d[1]也要變一下
}
void dp(int u,int fa){
	for(int i=0;i<ve[u].size();i++){
		int v=ve[u][i];
		if(v==fa)continue;
		d[v]=d[u]+cnt[1]-cnt[v]*2;
		dp(v,u);
	}
	ans=min(ans,d[u]);
}
int main(){
	cin>>n;int c,a,b;
	for(int i=1;i<=n;i++){
		cin>>c>>a>>b;
		w[i]=c;//注意輸入方式
		if(a)ve[i].push_back(a),ve[a].push_back(i);
		if(b)ve[i].push_back(b),ve[b].push_back(i);
	}
	dfs(1,0,0);
	dp(1,0);
	cout<<ans;
}

????????文章來源地址http://www.zghlxwxcb.cn/news/detail-856416.html

到了這里，關(guān)于【算法每日一練]-圖論（保姆級教程篇16 樹的重心 樹的直徑）#樹的直徑 #會議 #醫(yī)院設置的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！