算法模板(五)树基础算法

最小生成树

#include<bits/stdc++.h>
#define maxn 5000
#define maxm 10000
using namespace std;
inline char get(){
    static char buf[30],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
struct edge{
    int u,int v,int w,int next;
}E[maxm<<1];
bool cmp(edge a,edge b){
    return a.w<b.w;
}
int p[maxn],eid;
inline void init(){
    for(register int i=0;i<maxn;i++)p[i]=-1;
    eid=0;
}
int get(int x){
    if(fa[x]==x)return x;
    return fa[x]=get(fa[x]);
}
inline void insert(int u,int v,int w){
    E[eid].u=u;
    E[eid].v=v;
    E[eid].w=w;
    E[eid].next=p[u];
    p[u]=eid++;
}
inline void insert2(int u,int v,int w){
    insert(u,v,w);
    insert(v,u,w);
}
inline int kru(int n,int m){
    int sum=0;
    for(register int i=0;i<=n;i++)fa[i]=i;
    sort(E,E+m,cmp);
    for(register int i=0;i<m;i++){
        int u=get(E[i].u);
        int v=get(E[i].v);
        if(u!=v){
            fa[v]=u;
            sum+=E[i].w;
        }
    }
}
int main(){
    n=read();m=read();
    for(register int i=0;i<m;i++)E[i].u=read(),E[i].v=read(),E[i].w=read();
    cout<<kru(n,m);
    return 0;
}

求树的直径

#include<bits/stdc++.h>
#define maxn 2000
#define maxm 2000
using namespace std;
struct edge{
    int u,v,w,next;
};
int p[maxn],eid;
inline void init(){
    for(register int i=0;i<maxn;i++)p[i]=-1;
    eid=0;
}
inline void insert(int u,int v,int w){
    E[eid].u=u;
    E[eid].v=v;
    E[eid].w=w;
    E[eid].next=p[u];
    p[u]=eid++;
}
inline void insert2(int u,int v,int w){
    insert(u,v,w);
    insert(v,u,w);
}
int maxlen,point;
void dfs(int u,int pre,int step){
    if(maxlen!=step){
        maxlen=step;
        point=u;
    }
    for(register int i=p[u];~i;i=E[i].next){
        if(E[i].v!=pre){
            dfs(E[i].v,u,step+1);
        }
    }
}
int diamonted(){
    maxlen=-1;
    diameter(1,0,0);
    maxlen=-1;
    diameter(point,0,0);
}
int n,m;
int main(){
    cin>>n>>m;
    int u,v,w;
    for(register int i=0;i<m;i++){
        cin>>u>>v>>w;
        insert2(u,v,w);
    }
    cout<<diameter();
}

求树的重心

#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 10000;
struct edge {
    int v, next;
    int len;
} E[MAX_M];
int p[MAX_N], eid;
void init() {
    memset(p, -1, sizeof(p));
    eid = 0;
}
void insert(int u, int v) {
    E[eid].v = v;
    E[eid].next = p[u];
    p[u] = eid++;
}
int n;
int minNode=-1,minBalance=MAX_N;
int dfs(int u,int pre){
    int sz=0,maxSubtree=0;
    for(int i=p[u];i!=-1;i=E[i].next){
        if(E[i].v!=pre){
            int son=dfs(E[i].v,u);
            sz+=son;
            maxSubtree=max(maxSubtree,son);
        }
    }
    sz++;
    maxSubtree=max(maxSubtree,n-sz);
    if(maxSubtree<minBalance){
        minBalance=maxSubtree;
        minNode=u;
    }
    return sz;
}
int main() {
    cin>>n;
    init();
    for(int i=0;i<n-1;i++){
        int u,v;
        cin>>u>>v;
        insert(u,v);
        insert(v,u);
    }
    dfs(1,0);
    cout<<minNode<<endl;
    return 0;
}