整理的演算法模板合集： ACM模板
目錄
- 一、樹的直徑
- 樹形DP
- 兩次DFS / BFS（找到直徑的兩個端點）
- 二、動態修改樹的邊權并求每個時刻的直徑（線段樹）
- 三、樹的重心
一、樹的直徑
樹的直徑滿足如下性質：
-
若有多條直徑，則所有的直徑之間皆有公共點，
-
直徑的兩端一定是葉子，
-
樹中距離某一直徑端點最遠的點，至少有一個是該直徑的另一個端點，
-
對于樹上任意一個點，與之距離最遠的一個點，至少有一個直徑的端點，
給你一個無權無向的樹，撰寫程式以輸出該樹中最長路徑（從一個節點到另一個節點）的長度，在這種情況下，路徑的長度是我們從開始到目的地的遍歷邊數，
樹形DP
O ( n ) O(n) O(n)
const int N = 50007, M = 500007, INF = 0x3f3f3f3f;
int n, m, F[N], D[N], ans ;
int ver[N], nex[M], head[N], edge[N], tot;
bool vis[N];
void add(int x, int y, int z)
{
ver[tot] = y;
edge[tot] = z;
nex[tot] = head[x];
head[x] = tot ++ ;
}
void dp(int x){
vis[x] = 1;
for(int i = head[x] ;~i; i =nex[i]){
int y = ver[i], z = edge[i];
if(vis[y])continue;
dp(y);
ans = max(ans, D[x] + D[y] + z);
D[x] = max(D[x], D[y] + z);
}
}
int main(){
scanf("%d", &n);
memset(head, -1, sizeof head);
for(int i = 1; i < n; ++ i){
int x, y;
scanf("%d%d", &x, &y);
add(x, y, 1), add(y, x, 1);
}
dp(1);
printf("%d\n", ans);
return 0;
}
兩次DFS / BFS（找到直徑的兩個端點）
O ( n ) O(n) O(n)
//兩次dfs一次求P一次求Q
void dfs(int u,int &ed){
if(dis[u] > ans)ans = dis[u],ed = u;
vis[u] = 1;
for(int i = head[u];~i;i = nex[i]){
int v = ver[i],w = edge[i];
if(vis[v])continue;
dis[v] = dis[u] + w;
dfs(v,ed);
}
return ;
}
int p,q;
void solve(){
dfs(1,p);
ans = dis[p] = 0;
memset(vis,0,sizeof vis);
dfs(p,q);
cout << ans << endl;
}
在一棵無根樹上，找 A , B , C A,B,C A,B,C三個點，使得 A B + B C ( A C > B C ) AB+BC(AC>BC) AB+BC(AC>BC)或 A C + A B ( B C > A C ) AC+AB(BC>AC) AC+AB(BC>AC)最大，
我們假設 A C > B C AC>BC AC>BC，那么答案就是找到最大 A B + B C AB+BC AB+BC簡單貪心一下，先令AB最大，然后再找一個相應的最大的BC，強調要滿足(AC>AB)所以我們首先找出樹的直徑，然后列舉除了兩個端點外的點 C C C，使得 m i n ( A C , B C ) min(AC,BC) min(AC,BC)最大，答案就是樹的直徑 + m i n ( A C , B C ) +min(AC,BC) +min(AC,BC)
typedef long long ll;
const int N = 500007, M = 5000007, INF = 0x3f3f3f3f;
int n, m;
ll d[N], copy_d[N];
bool vis[N];
int head[N], ver[M], nex[M], edge[M], tot;
void add(int x, int y, int z)
{
ver[tot] = y;
edge[tot] = z;
nex[tot] = head[x];
head[x] = tot ++ ;
}
int bfs(int S)
{
queue<int>q;
memset(d, 0, sizeof d);
memset(vis, 0, sizeof vis);
//while(q.size())q.pop();
q.push(S), vis[S] = 1;
int maxx = 0, maxid;
while(q.size()){
int x = q.front();
q.pop();
for(int i = head[x]; ~i; i = nex[i]){
int y = ver[i], z = edge[i];
if(vis[y])continue;
vis[y] = 1;
d[y] = d[x] + z;
q.push(y);
if(d[y] > maxx){
maxx = d[y];
maxid = y;
}
}
}
return maxid;
}
int main()
{
scanf("%d%d", &n, &m);
memset(head, -1, sizeof head);
for(int i = 1; i <= m; ++ i){
int x, y, z;
scanf("%d%d%d", &x, &y, &z);
add(x, y, z);
add(y, x, z);
}
int p, q;
p = bfs(1);
q = bfs(p);
ll ans = d[q];//the length of AB
for(int i = 1; i <= n; ++ i){
copy_d[i] = d[i];
}
bfs(q);
ll res = 0;
for(int i = 1; i <= n; ++ i){
res = max(res, min(d[i], copy_d[i]));//find the longest edges among the remaining edges
}
ans += res;
printf("%lld\n", ans);
return 0;
}
二、動態修改樹的邊權并求每個時刻的直徑（線段樹）
有一個n個點的帶權無向樹，q次操作，每次修改一條邊的權值，要求在每次修改后，輸出樹的直徑大小，強制在線，
/*lmx,rmx,lmi,rmi,ld,rd,lrd,ans前綴/后綴的最大/最小和，前綴右減左最大，
后綴右減左最大，兩端點必須選滿右減左最大，任意子串右減左最大*/
#include<bits/stdc++.h>
#define ls(a) ((a)<<1)
#define rs(a) ((a)<<1|1)
#define N 200001
#define int long long
using namespace std;
typedef long long ll;
#define G if(++ip==ie)if(fread(ip=ibuf,1,LL,stdin))
const int LL=1<<19;
char ibuf[LL],*ie=ibuf+LL,*ip=ie-1;
inline char nc(void){G;return *ip;}
//#define getchar nc
inline ll read(void){
char opt;ll flag=1,res=0;
while((opt=getchar())<'0'||opt>'9')if(opt=='-')flag=-1;
while(opt>='0'&&opt<='9'){res=(res<<3)+(res<<1)+opt-'0';opt=getchar();}
return res*flag;
}
int n,m,st[N],top,q;
struct edge{int to;ll v;int x;};vector<edge>g[N];
ll w,sum[N<<2],lmx[N<<2],rmx[N<<2],lmi[N<<2],rmi[N<<2],ld[N<<2],rd[N<<2],lrd[N<<2],ans[N<<2],lastans,p[N][2];
void pushup(int x){
sum[x]=sum[ls(x)]+sum[rs(x)];
lmx[x]=max(lmx[ls(x)],sum[ls(x)]+lmx[rs(x)]);
rmx[x]=max(rmx[rs(x)],sum[rs(x)]+rmx[ls(x)]);
lmi[x]=min(lmi[ls(x)],sum[ls(x)]+lmi[rs(x)]);
rmi[x]=min(rmi[rs(x)],sum[rs(x)]+rmi[ls(x)]);
ld[x]=max(ld[ls(x)],max(ld[rs(x)]-sum[ls(x)],lrd[ls(x)]+lmx[rs(x)]));
rd[x]=max(rd[rs(x)],max(sum[rs(x)]+rd[ls(x)],lrd[rs(x)]-rmi[ls(x)]));
lrd[x]=max(lrd[ls(x)]+sum[rs(x)],lrd[rs(x)]-sum[ls(x)]);
ans[x]=max(max(ans[ls(x)],ans[rs(x)]),max(ld[rs(x)]-rmi[ls(x)],rd[ls(x)]+lmx[rs(x)]));
}
inline void Build(int pos,int l,int r){
ll v;if(l==r)return sum[pos]=(v=st[l]),lmx[pos]=rmx[pos]=max(v,0ll),lmi[pos]=rmi[pos]=min(v,0ll),ld[pos]=rd[pos]=lrd[pos]=ans[pos]=v,void();
int mid=(l+r)>>1;
Build(ls(pos),l,mid),Build(rs(pos),mid+1,r);
pushup(pos);
}
inline void Change(int pos,int l,int r,int x,ll v){
if(l==r)return sum[pos]=v,lmx[pos]=rmx[pos]=max(v,0ll),lmi[pos]=rmi[pos]=min(v,0ll),ld[pos]=rd[pos]=lrd[pos]=ans[pos]=v,void();
int mid=(l+r)>>1;
(x<=mid)?Change(ls(pos),l,mid,x,v):Change(rs(pos),mid+1,r,x,v);
pushup(pos);
}
inline void dfs(int x,int prt){
int y;for(auto t:g[x])if((y=t.to)^prt)st[*p[t.x]=++top]=t.v,dfs(y,x),st[p[t.x][1]=++top]=-t.v;
}
signed main(void){
int i,x;ll y,z;n=read(),q=read(),w=read();
for(i=1;i<n;++i)x=read(),y=read(),z=read(),g[x].push_back({y,z,i}),g[y].push_back({x,z,i});
dfs(1,0);Build(1,1,top);
while(q--){
x=(read()+lastans)%(n-1)+1,y=(read()+lastans)%w;
Change(1,1,top,*p[x],y),Change(1,1,top,p[x][1],-y);
printf("%lld\n",lastans=ans[1]);
}
return 0;
}
三、樹的重心
重心的性質
- 以樹的重心為根時，所有子樹的大小都不超過整棵樹大小的一半，
- 把兩棵樹通過一條邊相連得到一棵新的樹，那么新的樹的重心在連接原來兩棵樹的重心的路徑上，
- 在一棵樹上添加或洗掉一個葉子，那么它的重心最多只移動一條邊的距離，
- 樹中所有點到某個點的距離和中，到重心的距離和是最小的；如果有兩個重心，那么到它們的距離和一樣，
- 一棵樹最多有兩個重心，且相鄰，
給定一棵樹,求樹的重心的編號以及重心洗掉后得到的最大子樹的節點個數size,如果size相同就選取編號最小的.
const int N = 50007, M = 500007, INF = 0x3f3f3f3f;
typedef long long ll;
int n, m;
int head[N], ver[M], nex[M], tot;
ll T;
int son[N], ans, pos;
bool vis[N];
void add(int x, int y)
{
ver[tot] = y;
nex[tot] = head[x];
head[x] = tot ++ ;
}
void dfs(int x)
{
vis[x] = 1, son[x] = 1;
int res = 0;
for(int i = head[x]; ~i; i = nex[i]){
int y = ver[i];
if(!vis[y]){
dfs(y);
son[x] += son[y];
res = max(res, son[y]);//x下面的子樹
}
}
res = max(res, n - son[x]);//x上面的子樹
if(res < ans || (res == ans && x < pos)){
ans = res, pos = x;
}
}
int main()
{
scanf("%lld", &T);
while(T -- ){
tot = 0;
memset(head, -1, sizeof head);
memset(vis, 0, sizeof vis);
ans = INF;
scanf("%d", &n);
for(int i = 1; i < n; ++ i){
int x, y;
scanf("%d%d", &x, &y);
add(x, y), add(y, x);
}
dfs(1);
printf("%d %d\n", pos, ans);
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/48663.html
標籤：其他