【算法】 前向星存图

前向星是一种特殊的边集数组。
不同于邻接表和邻接矩阵对顶点的处理，前向星存图处理的是边与边的关系。

int cnt;            //记录边的编号
int head[maxn];     //head[u]表示上一个以u为起点的边的编号，初始化-1
struct st           //储存边的信息
{
    int to;         //边的终点
    int w;          //边的权值
    int next;       //下一个同起点边的编号
} edge[maxn];

这里再解释一下head数组和edge数组:

edge[i]并不是表示第i个顶点，而是编号为i的边，edge结构体不包含边的起点，但包含了与该边同起点的边的编号。

head[u]记录最后一条以u为起点的边的编号；
若head[u]==-1，则说明没有以u为起点的边；
若head[u]!=1，则可以找到最后一条边的编号v，经由edge[v].next找到下一条边，直到next==-1。

inline void add(int u,int v,int w)            //加边
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs(int u,int pre)
{
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        dfs(v,u);
    }
}

以下是【每日一题】 Shortest Path 的ac代码：
题目：https://ac.nowcoder.com/acm/problem/13886

#include <iostream>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cctype>
#include <functional>
#include <string>
#include <cstring>
#include <sstream>
#include <deque>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> Q;

const int inf1=2e9+9;
const ll inf2=8e18+9;
const ll mol=998244353;
const int maxn=2e4+9;
const int maxx=1e9+9;

int n;
ll ans;
int cnt,head[maxn];
struct st{int to,w,next;} edge[maxn];

inline void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w=w;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

int dfs(int u,int pre)
{
    int cnt_=1;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(v==pre) continue;
        if(dfs(v,u))
        {
            cnt_++;
            ans+=edge[i].w;
        }
    }
    return cnt_%2;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        cnt=0;
        memset(head,-1,sizeof head);
        scanf("%d",&n);
        for(int i=0;i<n-1;i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add(u,v,w);
            add(v,u,w);
        }
        ans=0;
        dfs(1,0);
        printf("%lld\n",ans);
    }
}

当中要注意的是，对于无向边，每条边要储存两次，所以head和edge都要开原来的原来的两倍大小。