首页 > 其他分享 >[图论]树

[图论]树

时间：2023-08-12 23:11:40浏览次数：30  
标签：图论 dist fa int dfs dep lca

树

一、树的重心

概念和性质

（1）.概念

树的重心也叫树的质心。对于一棵树\(n\)个节点的无根树，找到一个点，使得把树变成以该点为根的有根树时，最大子树的结点数最小。换句话说，删除这个点后最大连通块（一定是树）的结点数最小。

（2）.性质

1.树中所有点到某个点的距离和中，到重心的距离和是最小的（实际应用中经常用到此性质）。

2.把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。

3.一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。

4.一棵树最多有两个重心，且相邻。

关于如何求树的重心？

求树的重心运用动态规划的思想，也就是树上跑DP。

先任选一个结点作为根节点，把无根树变成有根树,然后去\(dfs\)，在 \(dfs\) 中计算每个子树的大小，记录「向下」的子树的最大大小，利用总点数 - 当前子树（这里的子树指有根树的子树）的大小得到「向上」的子树的大小，然后就可以依据定义找到重心了。

Tips

树的重点可以说是树的平衡点，其使以它为根的树中所有的子树的节点数相近。

代码

//树的重点可以说是树的平衡点，其使以它为根的树中所有的子树的节点数相近
int d[N];
int ans;//ans是树的重心;
int maxn = N;

void dfs(int u,int fa)
{
	d[u] = 1;
	int mx = 0;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		d[u] += d[v];
		mx = max(mx,d[v]);
	}
	mx = max(mx,n-d[u]);
	if(mx<maxn)
		maxn = mx,ans = u;
	//若选取编号最小的节点，可更改为
	/*  if(mx<maxn||(mx==maxn&&ans>u))
		  maxn = mx,ans = u;
	*/
}

板子题：P1395 会议

法一：

距离和最小，恰好符合我们重心的性质。重心就是我们要求的点，在以重心为源点bfs求距离和即可。

求所有点到某个点的距离和最小，求出那个点和距离和。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4+10,M = 2e6+10;

int idx,n,road;
vector<int> e[N];
int dist[N];
bool vis[N];
int d[N];
int ans;//ans是树的重心;
int maxn = N;

void dfs(int u,int fa)
{
	d[u] = 1;
	int mx = 0;
	for(auto v:e[u])
	{
		if(v==fa)continue;
		dfs(v,u);
		d[u] += d[v];
		mx = max(mx,d[v]);
	}
	mx = max(mx,n-d[u]);
//	if(mx<maxn)
//		maxn = mx,ans = u;
//若选取编号最小的节点，可更改为
	  if(mx<maxn||(mx==maxn&&ans>u))
		  maxn = mx,ans = u;
}

void bfs(int s)
{
	queue<int>q;
	q.push(s);
	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		for(auto y:e[x])
		{
			if(vis[y]||y==s)continue;
			vis[y] = true;
			dist[y] = dist[x]+1;
			road += dist[y];
			q.push(y);
		}
	}
}


int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	dfs(1,0);
	bfs(ans);
	cout<<ans<<" "<<road<<endl;
	return 0;
}

法二：

或者也可以用换根dp来做，因为是无根树，我们考虑随便一个点当作根，此时的路径和是多少。然后考虑另一个点做根的情况。当然不用每次都求一次的。

如图考虑：![image-20230811175124074](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230811175124074.png)

如果把根从fa换到它的儿子u会发生什么事情？

对于非u的子树部分到u的距离比到fa的距离多出了：\(1*(n-sz[u])\)整个这一部分(圈起来的)都要加上\(fa->u\)这条边。

对于u的子树部分，那么相反的，会少了:\(1*sz[u]\)。那么\(f[u] = f[fa]+n-2*sz[u]\)

考虑清楚这个，接下来我们只需要先预处理出\(sz\)，再去求\(f\)数组就可以了。

由于\(f\)数组的递推关系，我们考虑先求出一个，因为是无根树，不妨求\(1\)为根的情况，这时候的\(f[1]\)等于其他点的深度和(注意-n，距离等于深度-1)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e4+10,M = 2e6+10;

int n;
vector<int> e[N];
int dist[N];
bool vis[N];
int d[N],sz[N],f[N];
//深度,子树大小，距离和
void dfs1(int u)
{
	sz[u] = 1;
	for(auto v:e[u])
	{
		if(d[v])continue;
		d[v] = d[u] + 1;
		dfs1(v);
		sz[u] += sz[v];
	}
}

void dfs2(int u,int fa)
{
	f[u] = f[fa]+n-2*sz[u];
	for(auto v:e[u])
	{
		if(v==fa)continue;
		dfs2(v,u);
	}
}


int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i = 1;i<=n-1;i++)
	{
		int x,y;
		cin>>x>>y;
		e[x].push_back(y);
		e[y].push_back(x);
	}
	d[1] = 1;
	dfs1(1);
	int maxn = 0,idx = 1;
	for(int i = 1;i<=n;i++)maxn += d[i];
	maxn -= n;
	f[1] = maxn;
	for(auto y:e[1])
		dfs2(y,1);
	for(int i = 2;i<=n;i++)
	{
		if(f[i]<maxn)maxn = f[i],idx = i;
	}
	cout<<idx<<" "<<maxn<<"\n";
	return 0;
}

二、树的直径

什么是树的直径？

树上任意两节点之间最长的简单路径即为树的「直径」

求法：2次dfs。第一次从随便一个点开始搜，搜到最远的点，然后从这个最远的点再搜一次。得到的链就是树的直径。

//树的直径
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
std::vector<int>edges[N+1];
int n,l,pre[N+1],c[N+1],dist[N+1];

inline void dfs(int x)
{
	for(auto y:edges[x])
	{
		if(y!=pre[x])
		{
			pre[y] = x;
			dist[y]= dist[x]+1;
			dfs(y);
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i = 1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		edges[x].push_back(y);
		edges[y].push_back(x);
	}
	memset(dist,0,sizeof(dist));
	memset(pre,0,sizeof(pre));
	pre[1] = -1;
	dfs(1);
	int idx = 0,v =0;
	for(int i =1 ;i<=n;i++)
	{
		if(dist[i]>v)
		{
			v = dist[i],idx = i;
		}
	}
	memset(dist,0,sizeof(dist));
	memset(pre,0,sizeof(pre));
	pre[idx] = -1;
	dfs(idx);
	v =0;
	for(int i =1 ;i<=n;i++)
	{
		if(dist[i]>v)
		{
			v = dist[i];
		}
	}
	cout<<v<<"\n";
	return 0;
}

例题1：P5536 【XR-3】核心城市

题意：这 \(k\)座城市可以通过道路，在不经过其他城市的情况下两两相互到达。

定义某个非核心城市与这k座核心城市的距离为，这座城市与k座核心城市的距离的最小值。那么所有非核心城市中，与核心城市的距离最大的城市，其与核心城市的距离最小。你需要求出这个最小值。

思路：我们知道，直径是树里面最长的路径。我们要找到\(k\)个点，这\(k\)个点比如包括直径的中点（由于直径的定义其他点到中点的距离一定不大于直径两端到中点的距离(因为如果大于,就一定能找到一条比直径更长的路径）。我们以直径中点为根去\(dfs\),其他节点按照以自己为根的子树里面子树最大的深度-这个点的深度(\(maxdep_i-dep_i\))去从大到小排序(先把大的取了，消除掉)。连通性因为树边权为1，然后我们要选离中点远的点，那么离中点更近的肯定以及被选了(因为它更大)，那么选的话是连续的，那么连通性就有保证了。那么答案就是第\(k+1\)个（第一个不能被选的是答案，因为sort过了）。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
std::vector<int>edges[N+1];
int n,l,k,pre[N+1],c[N+1],dist[N+1];

inline void dfs(int x)
{
	for(auto y:edges[x])
	{
		if(y!=pre[x])
		{
			pre[y] = x;
			dist[y]= dist[x]+1;
			dfs(y);
		}
	}
}
int pos[N];
int dep[N],max_dep[N],ans[N];
void dfs2(int u,int fa)
{
	//if(edges[u].size()==0)max_dep[u] = dep[u];
	max_dep[u] = dep[u];
	for(auto v:edges[u])
	{
		if(v==fa)continue;
		dep[v] = dep[u] + 1;
		dfs2(v,u);
		max_dep[u] = max(max_dep[u],max_dep[v]);
	}
}
bool cmp(int x,int y)
{
	return x>y;
}


int main()
{
	ios::sync_with_stdio(false);cin.tie(0);	cout.tie(0);
	cin>>n>>k;
	for(int i = 1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		edges[x].push_back(y);
		edges[y].push_back(x);
	}
	memset(dist,0,sizeof(dist));
	memset(pre,0,sizeof(pre));
	pre[1] = -1;
	dfs(1);
	int idx = 0,v =0,p = 0;
	for(int i =1 ;i<=n;i++)
	{
		if(dist[i]>v)
		{
			v = dist[i],idx = i;
		}
	}
	memset(dist,0,sizeof(dist));
	memset(pre,0,sizeof(pre));
	pre[idx] = -1;
	dfs(idx);
	v = 0;
	for(int i =1;i<=n;i++)
	{
		if(dist[i]>v)
		{
			p = i;
			v = dist[i];
		}
	}
	int cnt = 0;
	while(p !=-1)
	{
		pos[++cnt] = p;
		p = pre[p];
	}
	
	int mid_pos = pos[(cnt+1)/2];
	dep[mid_pos] = 1;
	dfs2(mid_pos,0);
	for(int i = 1;i<=n;i++)
	{
		ans[i] = max_dep[i]-dep[i];
	}
	sort(ans+1,ans+1+n,cmp);
	cout<<ans[k+1]+1<<"\n";
	return 0;
}

三、树上差分

树上差分，什么意思嘞？就是树上做差分(feihua)。它有两种常见类型：1.边差分 2.点差分。

对于边差分裸题：给你一棵树，n次操作，每次把\(u..v\)路径上的权值加\(x\)，最后问你某两点的路径和。

对于\(u..v\)路径上的权值加\(x\)怎么实现呢？这里我们就用到的是差分。

图片引用自

img

\(dlt[u]+=x,dlt[v]+=x,dlt[lac]-=2x\),这样加的作用只限制于\(u..v\)，而对于\(lca\)的父亲是没有影响的。

对于点差分呢？和我们的边差分有所不同。

点差分裸题：有n次修改操作，每次把u..v的所有点权都加x，最后问点权最大的为多少。

我们与边差分不同的是，在\(lca\)处不是是\(dlt[lca]-=2x\)，而是\(dlt[lca]-=x\),然后\(dlt[fa[lca]]-=x\)。这是因为点权的话，\(lca\)这个点也是包含在里面的，需要被算一次。

\(u\)从左边过来给\(lca\)算了一次，然后\(v\)从右边过来又给\(lca\)算了一次，但我只需要一次，那么\(dlt[lca]-=x\)，而又不能蔓延到父亲，那\(fa[lca]-=x\)。

点差分模板题：[P3128 USACO15DEC] Max Flow P

四、树上LCA

  • 树上LCA板子
#include<bits/stdc++.h>
using namespace std;
const int N = 5000010;
const int LOGN = 20;
int n, m, root, dep[N], fa[N][LOGN + 2];
vector<int> e[N];
void dfs(int u, int from)
{
    dep[u] += dep[from] + 1;
    for(auto v : e[u]) {
        if(v == from) continue;
        fa[v][0] = u;
        dfs(v, u);
    }
}
void lca_init()
{
    for(int j = 1; j <= LOGN; j++)
        for(int i = 1; i <= n; i++)
            fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca_query(int u, int v)
{
    if(dep[u] < dep[v])   swap(u, v);
    int d = dep[u] - dep[v];
    for(int j = LOGN; j >= 0; j--)
        if(d & (1 << j))
            u = fa[u][j];
    if(u == v)    return u;
    for(int j = LOGN; j >= 0; j--)
        if(fa[u][j] != fa[v][j])
            u = fa[u][j],v = fa[v][j];
    return fa[u][0];
}
int main()
{
    cin>>n>>m>>root;
    for(int i = 2; i <= n; i++)
    {
        int u, v;    cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(root, 0);
    lca_init();
    while(m--)
    {
        int u, v;    cin>>u>>v;
        cout<<lca_query(u, v)<<endl;
    }
return 0;
}

几个经典例题：

例题1：P5836 Milk Visits S

做法1：

这个题的前置知识点：LCA，树上路径最值

树上路径最小值板子：路径最小值 

#include<bits/stdc++.h>
using namespace std;
const int N = 201000;
const int LOGN = 18;
vector<pair<int,int>>edge[N];
int n,q;
int val[N][LOGN+1],f[N][LOGN+1],dep[N];

void dfs(int u,int fa)
{
	dep[u] = dep[fa]+1;
	for(auto i:edge[u])
	{
		int v = i.first;
		if(v==fa)continue;
		f[v][0] = u;
		val[v][0] = i.second;
		dfs(v,u);
	}
}


int query(int u,int v)
{
	int ans = 1<<30;
	if(dep[u]>dep[v])
		swap(u,v);
	int d = dep[v]-dep[u];
	for(int j = LOGN;j>=0;j--)
	{
		if(d&(1<<j))
		{
			ans = min(ans,val[v][j]);
			v = f[v][j];
		}
	}
	if(u==v)return ans;
	for(int j = LOGN;j>=0;j--)
	{
		if(f[u][j]!=f[v][j])
		{
			ans = min({ans,val[u][j],val[v][j]});
			u = f[u][j],v = f[v][j];
		}
	}
	ans = min({ans,val[u][0],val[v][0]});
	return ans;
}


int main()
{
	cin>>n>>q;
	for(int i = 1;i<n;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		edge[u].push_back({v,w});
		edge[v].push_back({u,w});
	}
	dfs(1,0);

	for(int j = 1;j<=LOGN;j++)
	{
		for(int u = 1;u<=n;u++)
		{
			f[u][j] = f[f[u][j-1]][j-1];
			val[u][j] = min(val[u][j-1],val[f[u][j-1]][j-1]);
		}
	}
	for(int i = 1;i<=q;i++)
	{
		int u,v;
		cin>>u>>v;
		cout<<query(u,v)<<endl;
	}
	return 0;
}

对于本题：因为只有两种牛，我们对第一种牛标记为1，第二种标记为2。我们考虑把点的权值转化为边的权值。给出边的关系的时候，如果两个颜色一样那就标记这个颜色，否则标记为1+2 = 3。查询的时候如果是3，一定是yes，否则看是不是需要的就行。注意：如果给的是单点注意特判。

#include<bits/stdc++.h>
using namespace std;
const int N = 201000;
const int LOGN = 18;
vector<pair<int,int>>edge[N];
int n,m;
int val[N][LOGN+1],f[N][LOGN+1],dep[N];
int a[N];
void dfs(int u,int fa)
{
	dep[u] = dep[fa]+1;
	for(auto [v,w]:edge[u])
	{
		if(v==fa)continue;
		f[v][0] = u;
		val[v][0] = w;
		dfs(v,u);
	}
}


int query(int u,int v)
{
	int ans = 0;
	if(dep[u]>dep[v])
		swap(u,v);
	int d = dep[v]-dep[u];
	for(int j = LOGN;j>=0;j--)
	{
		if(d&(1<<j))
		{
			ans = max(ans,val[v][j]);
			v = f[v][j];
		}
	}
	if(u==v)return ans;
	for(int j = LOGN;j>=0;j--)
	{
		if(f[u][j]!=f[v][j])
		{
			ans = max({ans,val[u][j],val[v][j]});
			u = f[u][j],v = f[v][j];
		}
	}
	ans = max({ans,val[u][0],val[v][0]});
	return ans;
}


int main()
{
	cin>>n>>m;
	for(int i = 1;i<=n;i++)
	{
		char x;
		cin>>x;
		if(x=='H')
			a[i] = 1;
		else a[i] = 2;
	}
	for(int i = 1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		edge[u].push_back({v,(a[u]==a[v]?a[u]:a[u]+a[v])});
		edge[v].push_back({u,(a[u]==a[v]?a[u]:a[u]+a[v])});
	}
	dfs(1,0);
	
	for(int j = 1;j<=LOGN;j++)
	{
		for(int u = 1;u<=n;u++)
		{
			f[u][j] = f[f[u][j-1]][j-1];
			val[u][j] = max(val[u][j-1],val[f[u][j-1]][j-1]);
		}
	}
	for(int i = 1;i<=m;i++)
	{
		int u,v;
		char c;
		cin>>u>>v>>c;
		int t = query(u,v);
		if(u==v)
			t = a[u];
		//cout<<" t = "<<t<<endl;
		if(c=='H')
		{
			if(t==1||t==3)
				cout<<"1";
			else cout<<"0";
		}
		else
		{
			if(t==2||t==3)
				cout<<"1";
			else cout<<"0";
		}
	}
	cout<<endl;
	return 0;
}

做法2：并查集

因为题目只有两种牛，我们把颜色一样的放在一个连通块里面，查询的时候看他们的父亲一不一样，如果不一样，说明有两种。如果父亲一样，那看看是不是我们要的牛。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5010,M = 2e6+10;

int n,m,a[N];
struct DSU
{
	vector<int>fa,s;
	int cnt;//连通块数量.
	DSU(int n=1):fa(n+1,-1),s(n+1,1),cnt(n){}
	int size(int x){return s[find(x)];}
	int find(int x){return fa[x]==-1?x:fa[x]=find(fa[x]);}
	
	bool connect(int x,int y)
	{
		x=find(x),y=find(y);
		if(x==y)return true;
		else return false;
	}
	
	void merge(int x,int y)
	{
		x=find(x),y=find(y);
		if(x==y)return ;
		s[x]+=s[y];
		fa[y]=x;
	}
};


int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m;
	DSU dsu(n);
	string s;
	cin>>s;
	s = "?"+s;
	for(int i = 1;i<n;i++)
	{
		int x,y;
		cin>>x>>y;
		if(s[x]==s[y])dsu.merge(x,y);
	}
	for(int i = 1;i<=m;i++)
	{
		int x,y;
		char z;
		cin>>x>>y>>z;
		cout<<(!dsu.connect(x,y)||s[x]==z);
	}
	cout<<endl;
	return 0;
}

例题2：P3398 仓鼠找 sugar

结论:判断一个结点\(x\)是否在\(s-t\)路径上

  • \(dep[x]>=dep[LCA(s,t)]\)
  • \(LCA(s,x)=x\)或\(LCA(t,x)=x\)

比如问：\(a->b,c->d\)路径上是否有交

\(s = lca(a,b)\) \(t = lca(c,d)\)

\(if(dep[s]<dep[t])swap(s,t),swap(a,c),swap(b,d)\)

\(dep[s]\ge dep[t]\)

即\(dep[s]\ge dep[lcd(c,d)]\)

那么如果\(lca(s,c)==s||lca(s,d)==s\)那就是有交

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int LOGN = 20;
int n, m, root, dep[N], fa[N][LOGN + 2];
vector<int> e[N];
void dfs(int u, int from)
{
	dep[u] += dep[from] + 1;
	for(auto v : e[u]) {
		if(v == from) continue;
		fa[v][0] = u;
		dfs(v, u);
	}
}
void lca_init()
{
	for(int j = 1; j <= LOGN; j++)
		for(int i = 1; i <= n; i++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca_query(int u, int v)
{
	if(dep[u] < dep[v])   swap(u, v);
	int d = dep[u] - dep[v];
	for(int j = LOGN; j >= 0; j--)
		if(d & (1 << j))
			u = fa[u][j];
	if(u == v)    return u;
	for(int j = LOGN; j >= 0; j--)
		if(fa[u][j] != fa[v][j])
			u = fa[u][j],v = fa[v][j];
	return fa[u][0];
}

int dist(int a,int b) {return dep[a]+dep[b]-2*dep[lca_query(a,b)];}

int main()
{
	cin>>n>>m;
	for(int i = 2; i <= n; i++)
	{
		int u, v;    cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	lca_init();
	while(m--)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		/*
		  判断一个结点x是否在s-t路径上
		  - deep[x]>=deep[LCA(s,t)]
		  
		  - LCA(s,x)=x或LCA(t,x)=x;
		 */
		int s = lca_query(a,b);
		int t = lca_query(c,d);
		if(dep[s]<dep[t])
		{
			swap(s,t);
			swap(a,c);
			swap(b,d);
		}
		//dep[s]>=dep[t]
		//dep[s]>=dep[lca(c,d)]
		if(lca_query(s,c)==s||lca_query(s,d)==s)
			cout<<"Y\n";
		else cout<<"N\n";
		
	}
	return 0;
}

法二：判断两条路径是否有交
两个起点的距离 + 两个终点的距离 <= 两条路径的长度和
任意两点间距离\(a->b：dist[a]+dist[b]-2*dist[lca(a,b)]\)

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
const int LOGN = 20;
int n, m, root, dep[N], fa[N][LOGN + 2];
vector<int> e[N];
void dfs(int u, int from)
{
	dep[u] += dep[from] + 1;
	for(auto v : e[u]) {
		if(v == from) continue;
		fa[v][0] = u;
		dfs(v, u);
	}
}
void lca_init()
{
	for(int j = 1; j <= LOGN; j++)
		for(int i = 1; i <= n; i++)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
}
int lca_query(int u, int v)
{
	if(dep[u] < dep[v])   swap(u, v);
	int d = dep[u] - dep[v];
	for(int j = LOGN; j >= 0; j--)
		if(d & (1 << j))
			u = fa[u][j];
	if(u == v)    return u;
	for(int j = LOGN; j >= 0; j--)
		if(fa[u][j] != fa[v][j])
			u = fa[u][j],v = fa[v][j];
	return fa[u][0];
}

int dist(int a,int b) {return dep[a]+dep[b]-2*dep[lca_query(a,b)];}

int main()
{
	cin>>n>>m;
	for(int i = 2; i <= n; i++)
	{
		int u, v;    cin>>u>>v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	dfs(1, 0);
	lca_init();
	while(m--)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		
		
		/*
		  判断两条路径是否有交
		  两个起点的距离 + 两个终点的距离 <= 两条路径的长度和
		  
		  任意两点间距离a-b：dist[a]+dist[b]-2*dist[lca(a,b)]
		  
		 */
		if(dist(a,b)+dist(c,d)>=dist(a,c)+dist(b,d))
			cout<<"Y\n";
		else cout<<"N\n";
		
		
		
	}
	return 0;
}

标签：图论,dist,fa,int,dfs,dep,lca
From： https://www.cnblogs.com/nannandbk/p/17625810.html

相关文章

  • 【图论】最近公共祖先（LCA）
    什么是LCA最近公共祖先是相对于两个节点来说的，顾名思义，最近公共祖先即为两个节点公共的最近的祖先。如上图，\(86\)和\(67\)的\(LCA\)是\(75\)，\(67\)和\(27\)的\(LCA\)是\(50\)。怎么求LCA倍增法我们先想想暴力怎么做：从这两个节点开始，一步一步往上跳，直到跳到了一......
  • 图论2023年版
    图基本概念什么是图？图实际上是一个二元组\(G=(V,E)\)，其中V是图中所有的点形成的点集，而E是边集每一条边都可以描述成(u,v)，u和v都是V中的元素(v,w∈V)点数，即V中元素个数也称为G的阶图的分类图可以按照边有无方向分类，分为有向图和无向图无向图：每条边都是无向边的图称......
  • 图论一
    图论(1)图的存储直接存边inte[N];e[1]=3;//1->3有条边邻接表inth[N],e[N],ne[N],idx;voidadd(inta,intb){e[idx]=b,ne[idx]=h[a],h[a]=idx,idx++;}voidinit(){meset(h,-1,sizeof(h));//所有头结点为空}也可以用vectore[N];图的遍历树和图的深度......
  • Codeforces 1857D：Strong Vertices 与图论无关的出度最大统计
    1857D.StrongVerticesDescription:给定两个长度均为\(n\)的数组\(a\)和\(b\)（编号\(1\)~\(n\)），如果\(a_u-a_v\geqb_u-b_v\)\((u\neqv)\)，那么从\(u\)到\(v\)建立一条有向边。"Strong"定义为：一个点\(V\)可以经过有向图中合法的通路到达其他所有的点。请求解出"......
  • 图论学习笔记
    图图论绘图在线图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系!点一般用字母v表示，如v1，v2，v3，v4一些简单的术语：路径：一些边组成的序列，满足第一条边的终点......
  • 图论强联通分量（tarjan）算法
    图论强联通分量（tarjan）算法#include<bits/stdc++.h>usingnamespacestd;intn,m,cnt,cntb,ans;vector<int>edge[101];vector<int>belong[101];boolinstack[101];intdfn[101];intlow[101];stack<int>s;voidTarjan(intu){ ++cnt; dfn[u]=......
  • 【笔记】图论：网络流和二分图
    网络流的求法https://www.cnblogs.com/caijianhong/p/16863491.htmlmisc复杂度分析Dinic的复杂度上界为\(O(n^2m)\)。但是特殊情况下会更快，如二分图匹配是\(O(m\sqrtn)\)的；确定流量上限\(f\)时，复杂度为\(O(mf)\)。最小费用最大流的复杂度上界为\(O(nmf)\)。......
  • 图论提高
    复健\(Day7\)图论一\(DGA:\)有向无环图 \(SCC:\)强连通 \(BCC:\)双连通强联通：有向图中，两个顶点至少存在一条路径（两个顶点可以互相到达）强连通图：每两个顶点都强连通的有向图强连通分量：有向图的极大强连通子图\(1.\)有向图的强连通分量问题模型：对于一些存在依赖关系的模型，若......
  • 8.2 day9图论+dp
    100+70+70+20=260感觉如果时间够感觉还能写一下，结果T3超大数据结构写死了T1观察到最短路径仍然最优，直接dij即可，注意判断终点不用等红灯T2暴力是\(O(n^4)\)的，是dp，但是我写的是分层图，同样时间，还没有优化空间，寄设计\(dp_{i,j}\)为跳到\((i,j)\)所需最小花费每次从所有点转移，算......
  • 成都集训图论篇
    [NOI]网格题目描述跳蚤国王和蛐蛐国王在玩一个游戏。他们在一个\(n\)行$m$列的网格上排兵布阵。其中的\(c\)个格子中，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。我们称占据的格子有公共边的两只跳蚤是相邻的。我们称两只跳蚤是连通的，当且仅当这两只跳蚤相邻......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99