欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树与图论的相关题目

程序员文章站 2022-06-16 11:06:06
...

树与图论的相关题目

1.树上求和.

树与图论的相关题目

因为是一棵树,从任意一点为根节点搜索都可以搜索完所有边。这里以1为根节点搜索。递归保存每个边的贡献次数。按贡献的次数从小到大排序,然后权值从n-1
到1相乘求和即可。 一个重要的知识点:U—V的边的贡献次数 = size(以V为边的子树结点数目)*(N-size)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll n,ans[N],cnt;
vector<int>g[N];
ll dfs(int u,int fa){
	ll sz=1;
	for(auto v:g[u])
		if(v!=fa) sz+=dfs(v,u);
	ans[cnt++]=sz*(n-sz);
	return sz;
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1,0);
	sort(ans,ans+cnt);
	ll res=0;
	for(int i=n-1;i>0;i--) //res[0]是保存的以最后一个结点为起点的边的次数  显然没有为0 所以 i到1就够了 
		 res+=ans[n-i]*i;
		cout<<res<<endl;
	return 0;
} 

2.求树的直径

题目传送门:POJ1985模板题
下面上代码。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
#define mst(a) memset(a,0,sizeof a)
const int N=4e4+5;
struct edge{
	int to,nt,w;
}e[2*N];
int cnt,n,vis[N],h[N],d[N],m;//cnt记录边数,n顶点数,vis[i]标记结点i是否访问,h[i]头结点,d[i]保存到起点的最大距离 
void add(int u,int v,int w){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nt=h[u];
	h[u]=cnt++;
}
void bfs(int u){
	mst(vis),mst(d);
	queue<int>q;
	q.push(u);
	while(q.size()){
		u=q.front();q.pop();vis[u]=1;
		for(int i=h[u];i;i=e[i].nt)
		{
			int v=e[i].to,w=e[i].w;
			if(!vis[v])
			{
				d[v]=d[u]+w;
				vis[v]=1;
				q.push(v);
			}
		}
	} 
}
int main(){
		ios::sync_with_stdio(false),cin.tie(0);
		cin>>n>>m; 
		cnt=1;//从1开始 
		mst(h);
		for(int i=1;i<=m;i++)
		{
			int u,v,w;
			char c;
			cin>>u>>v>>w>>c;
			add(u,v,w);
			add(v,u,w);
		}
		bfs(1);
		int mx=0,p;
		for(int i=1;i<=n;i++) ///这里是为了找到树的直径的一个端点B 
			if(d[i]>mx)
			{
				mx=d[i];
				p=i;// p为端点B 
			}
		bfs(p); //将端点B作为起点开始BFS 
		mx=0;
		for(int i=1;i<=n;i++){///找到另一个端点。 
			if(d[i]>mx)
			{
				mx=d[i];
				p=i; ///此时的端点A为直径的另一个端点。 
			}
		}
		cout<<mx<<endl;
	return 0;
} 

3.求树的多源最长路。

题目传送门:HDU2196

思路:利用树的直径和BFS(或者DFS),这里我用双BFS求直径的两个端点。然后对每个结点取较大值。
原理:树的一个结点的最长路的终点一定是树直径的某一个端点。这里简单证明下:任取一点u ,假设u的最长路终点为v,
情况1:若u在树的直径上,则v必为直径的端点.
情况2:若u不在树的直径上,用反证法,假设v不是直径的端点,u----v的路径与最长路p-----q的交点为c,因为
d(u,c)+d(c,v)>d(u,c)+d(c,p) 所以 d(c,v)>d(c,p)
所以 d(c,v)+d(c,q)>d(c,p)+d(c,q)=d(p,q) 即d(v,q)>d(p,q)与d(p,q)最大矛盾,所以v一定是直径的端点.
下面上代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mst(a) memset(a,0,sizeof a)
const int N=1e4+5;
struct edge{
	int to,nt,w;
}e[2*N];
int cnt,n,vis[N],h[N],d[N],pre[N];//cnt记录边数,n顶点数,vis[i]标记结点i是否访问,h[i]头结点,d[i]保存到起点的最大距离 
void add(int u,int v,int w){
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nt=h[u];
	h[u]=cnt++;
}
void bfs(int u){
	mst(vis),mst(d);
	queue<int>q;
	q.push(u);
	while(q.size()){
		u=q.front();q.pop();vis[u]=1;
		for(int i=h[u];i;i=e[i].nt)
		{
			int v=e[i].to,w=e[i].w;
			if(!vis[v])
			{
				d[v]=d[u]+w;
				vis[v]=1;
				q.push(v);
			}
		}
	} 
}
int main(){
	while(cin>>n){
		cnt=1;//从1开始 
		mst(h);
		for(int i=2;i<=n;i++)
		{
			int v,w;
			cin>>v>>w;
			add(i,v,w);
			add(v,i,w);
		}
		bfs(1);
		int mx=0,p;
		for(int i=1;i<=n;i++) ///这里是为了找到树的直径的一个端点B 
			if(d[i]>mx)
			{
				mx=d[i];
				p=i;// p为端点B 
			}
		bfs(p); //将端点B作为起点开始BFS 
		mx=0;
		for(int i=1;i<=n;i++){///找到另一个端点。 
			if(d[i]>mx)
			{
				mx=d[i];
				p=i; ///此时的端点A为直径的另一个端点。 
			}
		 pre[i]=d[i];  //pre[i]表示 结点i到 直径的一个端点B的最大距离 
		}
		bfs(p);//求每个结点到直径的端点A的最大距离。 
		for(int i=1;i<=n;i++)
			printf("%d\n",max(pre[i],d[i])); //此时的d[i]表示结点i到树直径的另一个端点A的最大距离 
	}   ///因为结点i的最大路径的终点肯定为树的直径的某一个端点。所以可以用max(pre[i],d[i]) 求 
	return 0;
} 

求树的割点.

题目传送门:POJ1144模板题

割点和割边。
割点的两个定理:定理1若树T的根结点s为割点,当且仅当s有两个及其以上的子结点. (这几个部分会分成几个子树,也就够成了两个及其以上的连通分量,若只有一个子结点,去掉这个结点,只会有一个子树,也就是一个连通分量,所以不是割点。
定理2:若树T的非根结点s为割点,当且仅当s存在至少一个子结点v及其后代都没有回退边能连回到s的祖先. (反证:若所有子结点都能通过回退边连回s的根节点,则去掉s后。S的子树仍与原来的树连通,仍然为一个连通块。
若存在一个,则该子结点及其后代能成为一个连通块,就分成了两个及其以上的连通块。
编程判断方法: 割点: 非根结点:low[v]>=num[u]
根结点:u==1&&child>=2
割边:low[v]>num[u] (u的子结点v最多只能到v本身,不会到u及u的祖先.即u—v这条边是割边。

上代码。

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N=105;
#define mst(a) memset(a,0,sizeof a) 
int low[N],num[N],dfn,n;//dfn记录递归顺序.
bool vis[N];//标记是否为割点
vector<int> g[N];
void dfs(int u,int fa){
	low[u]=num[u]=++dfn;//初始值
	//printf("u=%d,fa=%d\n",u,fa);
	int child=0;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(!num[v]) //若v没有访问过 
		{
			child++;
			dfs(v,u);
			low[u]=min(low[v],low[u]);//用后代的返回值更新父结点的low值 
			//printf("low[%d]=%d,low[%d]=%d\n",u,low[u],v,low[v]);
			if(low[v]>=num[u]&&u!=1)//如果不是根节点且存在一个子结点没有回退边到u的祖先 
				vis[u]=1;
		}
		else if(num[v]<num[u]&&v!=fa) //处理回退边 即v能连接到u的祖先&&v是u的子结点 
		low[u]=min(low[u],num[v]);//说明u及其后代能通过回退边到u的祖先,更新low[u]
	 }
	 if(u==1&&child>=2) //如果是根结点则要求子结点数大于等于2 
	 	vis[u]=1; 
}
int main(){
	int u,v,ans;
		while(cin>>n&&n){
			mst(vis),mst(low),mst(num),dfn=ans=0; //初始化 
			for(int i=1;i<=n;i++) g[i].clear(); //初始化 
			 while(cin>>u&&u)
			 {
			 		while((getchar())!='\n')
			 		{
			 			 cin>>v;
			 			 g[u].push_back(v);
			 			 g[v].push_back(u);
 					}
			 }
			 dfs(1,0);
			 for(int i=1;i<=n;i++) ans+=vis[i];
			 cout<<ans<<endl;
		}
		return 0; 
}