树与图论的相关题目

树与图论的相关题目

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