首页 > 其他分享 >DAG与拓扑排序

DAG与拓扑排序

时间:2024-04-05 15:11:56浏览次数:22  
标签:食物链 DAG int 拓扑 入度 计数 include 排序

现实生活中我们经常要做一连串事情,这些事情之间有顺序关系或依赖关系,做一件事情之前必须先做另一件事,如安排客人的座位、穿衣服的先后、课程学习的先后等。这些事情可以抽象为图论中的拓扑排序(Topological Sorting)问题。

例题:P4017 最大食物链计数

给出一个食物网,要求出这个食物网中最大食物链的数量。这里的“最大食物链”,指的是生物学意义上的食物链,即开头是不会捕食其他生物的生产者,结尾是不会被其他生物捕食的消费者。答案可能很大,所以要对 \(80112002\) 取模。

分析: 考虑把这个食物网转换为一个图,食物网有什么样的特点呢?

  1. 食物网中的捕食关系一定是单向的(比如猫吃鱼,而不是鱼吃猫)。
  2. 食物网中的捕食关系一定是无环的,不存在 A 捕食 B,B 捕食 C,C 捕食 A 这种情况。

所以可以发现食物网其实就是一个 DAG(有向无环图)。在这道题目中“最大食物链”的定义就是一条从入度为 \(0\) 的点开始到出度为 \(0\) 的点结束的链,即要计算这样的链的个数。

image

用一个数组 f[x] 表示从任意一个入度为 0 的点到点 x 的食物链计数。那么对于任意一个入度为 0 的点 y,它的 f[y]=1。对于一个入度非 0 的点 z,它的 f[z] 等于能到达点 z 的点 u 的 f[u] 之和。

如点 3,它的食物链计数等于点 1 的食物链计数加上点 10 的,即 f[3]=f[1]+f[10]=1+1=2。而对于点 6,它的食物链计数等于点 2 的食物链计数加上点 3 的,即 f[6]=f[2]+f[3]=1+2=3。这样最后只要对所有出度为 0 的点的事物链计数求和就能求出题目所求的答案了。

在计算 f[x] 的过程中,需要保证对于点 x,所有能到达点 x 的点 y 的 f[y] 已经被计算过了,这样就需要确定一个合适的计算顺序。这种方法叫做 拓扑排序。拓扑排序并不是对一个数列进行排序,而是在 DAG 上对点进行排序,使得在搜到点 x 时所有能到达点 x 的点 y 的结果已经计算完成了。具体流程如下:

  1. 将所有入度为 0 的点加入处理队列。
  2. 将处于队头的点 x 取出,遍历点 x 能到达的所有点 y。
  3. 对于每一个 y,删去从点 x 到点 y 的边。在具体的实现中,只需要让 y 的入度减一即可。在这一步中,顺便可以对点 y 的数据进行维护,在这题中是 f[y]=(f[y]+f[x])%MOD
  4. 如果点 y 的入度减到 0 了,说明所有能到 y 的点都被计算过了,这时将点 y 加入处理队列。
  5. 重复步骤 2 直到处理队列为空。

这样,就保证了在食物链计数这题中求 f[x] 的顺序正确。代码如下:

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 5005;
const int MOD = 80112002;
vector<int> graph[N];
int ind[N], f[N];
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b; scanf("%d%d", &a, &b);
        graph[a].push_back(b); // 存边
        ind[b]++; // 点b的入度+1
    }
    queue<int> q;
    for (int i = 1; i <= n; i++) 
        if (ind[i] == 0) {
            q.push(i); f[i] = 1; // 将入度为0的点加入队列
        }
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : graph[u]) {
            f[v] = (f[v] + f[u]) % MOD;
            ind[v]--;
            if (ind[v] == 0) q.push(v); // 此时点y的依赖都解除了,将点y加入队列
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) 
        if (graph[i].size() == 0) ans = (ans + f[i]) % MOD;
    printf("%d\n", ans);
    return 0;
}

答案需要对 80112002 取模,在计算 f 时一边加一边取模,以及在对出度为 0 的点的食物链计数求和时一边加一边取模。如果只在输出答案时取模,那么可能在累加的过程中答案超出了数据类型存储的范围而导致答案的错误。

例题:P1983 [NOIP2013 普及组] 车站分级

对于每趟车次而言,不停的站级别要小于停靠的车站,因此可以将问题建模为所有停靠的车站向不停的车站连有向边,则至少需要的等级数量等于最长链的边数加 1。

这里的建图还可以进一步优化,对于每一趟车次可以增加一个虚拟结点,所有停靠的车站指向这个虚拟结点,而虚拟结点又指向所有不停靠的车站,这样可以将建图的边数由 \(|S_1| \times |S_2|\) 降至 \(|S_1| + |S_2|\),其中 $|S_1| $ 和 $ |S_2|$ 分别为停靠车站的数量和不停靠车站的数量。这样的话答案为最长链的边数除以 2 再加 1。

#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
const int N = 2005;
vector<int> graph[N];
int ind[N], level[N];
int main()
{
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int s; scanf("%d", &s);
        // virtual node (n+i)
        int pre = 0;
        for (int j = 1; j <= s; j++) {
            int stop; scanf("%d", &stop);
            if (j == 1) pre = stop;
            graph[stop].push_back(n + i); ind[n + i]++;
            for (int k = pre + 1; k < stop; k++) {
                graph[n + i].push_back(k);
                ind[k]++;
            }
            pre = stop;
        }
    }
    queue<int> q;
    int ans = 1;
    for (int i = 1; i <= n + m; i++) 
        if (ind[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : graph[u]) {
            level[v] = max(level[v], level[u] + 1);
            ans = max(ans, level[v]);
            ind[v]--;
            if (ind[v] == 0) q.push(v);
        }
    }
    printf("%d\n", ans / 2 + 1);
    return 0;
}

标签:食物链,DAG,int,拓扑,入度,计数,include,排序
From: https://www.cnblogs.com/ronchen/p/18115473

相关文章

  • 信息学奥赛一本通题目解析:1938:【07NOIP普及组】奖学金(排序)
    【题目描述】某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前55名学生发奖学金。期末,每个学生都有33门课的成绩:语文、数学、英语。先按总分从高到低排序,如果两个同学总分相同,再按语文成绩从高到低排序,如果两个同学总分和语文成绩都相同,那么规定学号小的同学......
  • 用Java实现快速排序
    快速排序(QuickSort)是一种分治的排序算法。它的基本思想是:选择一个基准元素(本文选择第一个元素)。将数组中比基准小的元素放在基准的左边,比基准大的元素放在基准的右边。对基准左边和右边的子数组分别进行快速排序。快速排序的优点包括:高效性:平均时间复杂度为O(nlogn)。适......
  • 九、算法-排序-堆排序
    常见六大排序:冒泡、选择、插入、快速、归并、堆。在了解堆排序之前,需要了解数据结构-二叉树的知识。二叉树:树中的每个节点下最多只有两个叶子节点;根节点:二叉树的首个节点;叶子节点:非根的节点;父节点-子节点:父节点下方归属的为子节点,是相对而言的关系,在顺序存储的数据结构里......
  • 归并排序 返回逆序数 python
    defmerge_sort_and_count_inversions(arr):n=len(arr)ifn<=1:returnarr,0#如果n小于等于1,数组已经有序,直接返回数组本身和逆序数0mid=n//2left_lst,inv_left=merge_sort_and_count_inversions(arr[:mid])#对左半部分进行递......
  • P2824 [HEOI2016/TJOI2016] 排序
    简要题意给定一个长度为\(n\)的排列\(a\),有\(m\)次操作:将\([l,r]\)从小到大排序将\([l,r]\)从大到小排序求\(m\)次操作后\(a_q\)的值。\(n,m\leq10^5\)思路首先这种排序的数据结构没有什么想法,根本原因是因为值太多了。但是我们观察到这是一个排列,这对于解......
  • 插入排序
    #include<bits/stdc++.h>usingnamespacestd;intmain(){ inta[]={7,4,8,9,2,6}; for(inti=1;i<6;i++){ for(intj=i;j>0;j--){ if(a[j]<a[j-1]){ swap(a[j],a[j-1]); }else{ break; } } } for(inti=0;i<6;i......
  • 插入排序
    //基本思想:把要排序的数组分为已排序和未排序两部分再从未排序的部分中逐个去除元素//把它和已排序元素比较//从右向左比较,如果右边比左边小,交换,否则跳出循环,进行下一次比较//得到一个按升序排列的有序数组//这种算法叫插入排序#include<iostream>usingnamespacestd;......
  • 插入排序
    #include<bits/stdc++.h>usingnamespacestd;intmain(){intn;cin>>n;inta[n+5];for(inti=1;i<=n;i++){cin>>a[i];}intj;for(inti=2;i<=n;i++){j=i;while(a[j]<a[j......
  • 插入排序
    #include<iostream>usingnamespacestd;intmain(){ inta[10]={99,1,2,3,164,5,6,71,8,4}; intmax; for(inti=1;i<10;i++){ for(intj=i;j>0;j--){ if(a[j-1]>a[j]){ swap(a[j],a[j-1]); }else{ break; } } } for(inti=0;i......
  • 选择排序
    //基本思想:从数组的未排序区域选出一个最小的元素,//把它与数组中的第一个元素交换位置://然后再从剩下的未排序区域选出一个最小的元素,//把它与数组中的第二个元素交换位置//重复上述过程,直到数组中的所有元素按升序排列完成#include<iostream>usingnamespacestd;int......