边表 | Axell's Blog

边表

Axell 8月 26, 2018

边表

储存边的表格,通常用于图论题中点较多,但边较少的情况

代码实现

变量初始化

int head[MAXN],Next[MAXM],a[MAXM],v[MAXM],cnt;
  //head: 从这个点出发的第一条边的编号 Next: 与这条边有相同的起点的下一条边的编号
  //a[i]: 第i条边的终点 v[i]: 第i条边的权值 cnt: 当前边的总数

初始化(init)

    for (int i=1;i<=n;++i)
        head[i]=-1;

遍历从一个点出发的所有边(visit)

    for (int i=head[st];i!=-1;i=Next[i]){...}

加入一条边(add)

void add(int st,int en){
    cnt++;  //总数++
    Next[cnt]=head[st];  //将新加入的这条边的下一条边指向原来的第一条边
    head[st]=cnt;  //将第一条边指向新加入的这条边,类似于链表
    a[cnt]=en;  //配置边的信息
}

例题

K部门

题目描述

BSNY进入了一个大公司实习，这个公司有很多部门，部门下面又有子部门，整个部门结构是一棵树。也就是有一个大老板，老板管理很多大部门的经理，每个大部门的经理管理小部门的经理，直到最底层的员工。

总所周知，上级的上级可以管下级，也就是说，某个经理可以管理它部门下面的经理及底层。如果一个人能管理的人数刚好到达K，我们称这个部门是K部门。

为了描述方便，我们将公司内所有人编号1-N，大老板编号为1。

给定公司管理的树，问公司内有多少个K部门？

输入

第一行输入N, K

接下来N-1行，每行输入A, B，表示A可以管B

输出

输出有多少个K部门

样例输入

样例输出

提示

【样例说明】

2管4，5两个人，3管6，7两个人

1管下面所有人，所以2部门为2，3所在的部门，有2个

【数据规模和约定】

30%的数据 1<=N<=100

60%的数据 1<=N<=10000

100%的数据 1<=N<=100000, 1<=A, B<=N, 0<=K<N

代码

#include <bits/stdc++.h>
using namespace std;

int head[100005],Next[100005],a[100005],d[100005],cnt,n,m,t1,t2,ta;

void add(int st,int en){
    cnt++;
    Next[cnt]=head[st];
    head[st]=cnt;
    a[cnt]=en;
}

void bl(int st){
    d[st]=1;  //d中储存该人所管的人(包括自己),所以先初始化为1
    for (int i=head[st];i!=-1;i=Next[i]){
        bl(a[i]);
        d[st]+=d[a[i]];  //回溯
    }
    if (d[st]==m+1) ta++;  //累加ans
}

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i)
        head[i]=-1;
    for (int i=1;i<=n-1;++i){
        scanf("%d %d",&t1,&t2);
        add(t1,t2);
    }
    bl(1);
    cout<<ta;
    return 0;
}

拉力赛

题目描述

车展结束后，游乐园决定举办一次盛大的山道拉力赛，韵韵自然也要来参加大赛。

赛场上共有n个连通的计时点，n-1条赛道（构成了一棵树）。每个计时点的高度都不相同（父结点的高度必然大于子结点），相邻计时点间由赛道相连。由于马力不够，所以韵韵的遥控车只能从高处驶向低处。而且韵韵的车跑完每条赛道都需花费一定的时间。

举办方共拟举办m个赛段的比赛，每次从第u个计时点到第v个计时点，当然其中有不少比赛韵韵的遥控车是不能参加的（因为要上坡）。平平想知道他能参加多少个赛段的比赛，并且想知道他完成这些赛段的总用时。

赛道皆为单向。

结点1是根节点，最高。

输入

第一行两个整数n，m。

接下来n-1行每行3个整数a、b、t。

表示韵韵的遥控车可以花t秒从第a个计时点到第b个计时点。

接下来m行每行2个整数u、v，意义如描述所示。

输出

第一行输出一个正整数，表示能参加的赛段数。

第二行输出一个正整数，表示总用时。

样例输入

样例输出

1
2

提示

【数据规模和约定】

输入可能是无向图

u≠v；

答案小于2^64。

N<=10000

M<=100000

代码

#include <bits/stdc++.h>
using namespace std;
#define M 100005


int head[M],Next[M],a[M],c[M],intime[M],outtime[M],cnt,n,m,t1,t2,t3,ta2,dfst;  //这里的数组定义的有一些问题,不过也能过,边数为2*M,节点数不是M
                               //intime,outtime表示时间戳
long long dep[M],ta; //dep[i]表示i到root的距离

void add(int st,int en,int val){
    cnt++;
    Next[cnt]=head[st];
    head[st]=cnt;
    a[cnt]=en;
    c[cnt]=val;
}

void bl(int st,int pre){
    dfst++;  //时间++
    intime[st]=dfst;  //记录入时间
    for (int i=head[st];i!=-1;i=Next[i]){
        if (a[i]==pre) continue;  //如果是通向父节点的路径就跳过
        dep[a[i]]+=dep[st]+c[i];
        bl(a[i],st);
    }
    dfst++;
    outtime[st]=dfst;  //记录出时间
}

bool check(int t1,int t2){
    return (intime[t2]>=intime[t1]&&outtime[t2]<=outtime[t1]);  //注意只能t1->t2,不能t2->t1
}  //判断上下坡

int main(){
    cin>>n>>m;
    for (int i=1;i<=n;++i)
        head[i]=-1;
    for (int i=1;i<=n-1;++i){
        scanf("%d %d %d",&t1,&t2,&t3);
        add(t1,t2,t3);
        add(t2,t1,t3);  //无向图要加2条边
    }
    bl(1,0);

    for (int i=1;i<=m;++i){
        scanf("%d %d",&t1,&t2);
        if (check(t1,t2)){
            ta2++;
            ta+=abs(dep[t1]-dep[t2]);
        }
    }
    cout<<ta2<<endl<<ta;
    return 0;
}

本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/9/