1. Toy模板网首页
  2. > Toy博客

第三章 图论 No.9有向图的强连通与半连通分量

9月前 作者：.SacaJawea 分类：Toy博客 阅读(48) 违法举报

这篇具有很好参考价值的文章主要介绍了第三章 图论 No.9有向图的强连通与半连通分量。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

定义

连通分量是无向图的概念，yxc说错了，不要被误导
强连通分量：在一个有向图中，对于分量中的任意两点u，v，一定能从u走到v，且能从v走到u。强连通分量是一些点的集合，若加入其他点，强连通分量中的任意两点就不能互相递达
半连通分量：在一个有向图中，对于分量中的任意两点u，v，一定存在从u走到v或者从v的路径

应用：通过缩点（将所有强连通分量缩成一个点）的方式，那么一个有向图就转换成了一个有向无环图DAG（拓扑图）
对于拓扑图，可以直接用bfs求最短路问题

第三章 图论 No.9有向图的强连通与半连通分量,AcWing算法提高课 课程记录,图论,深度优先,算法

  1. 树枝边（x和y直接相连）
  2. 前向边（y是x的祖先节点）
  3. 后向边（前向边的反）
  4. 横叉边（指向已经遍历过的其他分支上的点）

树枝边是一种特殊的前向边
第三章 图论 No.9有向图的强连通与半连通分量,AcWing算法提高课 课程记录,图论,深度优先,算法

强连通分量简称scc，如何判断当前点是否在scc中？

  1. 存在一条后向边，指向祖先节点
  2. 先走横叉边，横叉边连接了后向边

无论如何，其一定能走到已经遍历过的祖先节点上
点可能存在自环，也是强连通分量（书上说自环不是强连通分量，但是为了算法的实现，将自环认为是强连通分量）

Tarjan求SCC

给定时间戳的概念，从小到大的时间为dfs的顺序
那树枝边的y一定比x大1，前向边的y一定大于等于x+1
后向边的y一定小于x，横叉边也是
对每个点定义两个时间戳：
dfs[u]表示遍历到u的时间
low[u]表示从u开始走，能遍历到的最小时间戳
若u是强连通分量的最高点，那么dfn[u] == low[u]，即该点无法再往上走到其他点

板子中使用了两个栈，一个是系统函数栈，用来深搜。一个是自定义的栈，保存当前正在遍历的强连通分量中的所有点

板子 O ( n + m ) O(n + m) O(n+m)：

void tarjan(int x)
{
	dfn[x] = low[x] = ++ tp;
	stk[ ++ tt] = x, st[x] = true;
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int y = e[i];
		if (!dfn[y])
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if (st[y]) low[x] = min(low[x], dfn[y]);
	}
	if (low[x] = dfn[x])
	{
		int y;
		++ cnt;
		do{
			y = stk[tt -- ]， st[y] =false;
			id[y] = cnt;
		} while (y != x)
	}
}

缩点：遍历所有点，再遍历其所有邻点，若两点不在同一强连通分量中，将这两点之间添加一条边
强连通分量编号递减的顺序一定是拓扑序，求拓扑序一般使用bfs，除此之外还能使用dfs
遍历所有点，从入边为0的点开始，dfs其所有邻点，完成后将该点的编号加入序列中，序列的逆序就是拓扑序。因为每次进入序列的点一定无后继（或者后继节点已经进入序列的点）
不过，若图中存在多个入边为0的点，选择其一进行dfs即可，后续要在拓扑序开头加上这几个入边为0的点

1174. 受欢迎的牛

1174. 受欢迎的牛 - AcWing题库
第三章 图论 No.9有向图的强连通与半连通分量,AcWing算法提高课 课程记录,图论,深度优先,算法

反向建图，遍历所有点，用bfs判断当前点是否能递达其他所有点，时间复杂度为 O ( n 2 ) O(n^2) O(n2)
如果不反向建图，就要判断图中有几个出边为0的点，若有1个，那么这个点就是最受欢迎的，若有>1个，那么不存在最受欢迎的点，若有0个，说明图中一定存在环（强连通分量），环中的节点数量为受欢迎的点的数量

将所有的强连通分量（环）缩成一个点，此时图中出边为0的点的数量不可能为0
只要判断数量是否为1即可
若出边为的点的数量为1，说明该强连通分量中的所有点都是受欢迎的，统计环中节点的数量即可

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e4 + 10, M = 5e4 + 10;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int stk[N], tt; bool st[N];
int dout[N], id[N], sz[N]; // 每个强连通分量中的节点数量
int n, m;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x)
{
    stk[ ++ tt] = x, st[x] = true;
    dfn[x] = low[x] = ++ tp;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (st[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int y;
        cnt ++ ;
        do {
            y = stk[tt -- ], st[y] = false;
            id[y] = cnt;
            sz[cnt] ++ ;
        } while (y != x);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        add(x, y);
    }
    
    for (int i = 1; i <= n; ++ i )
        if (!dfn[i]) tarjan(i);
        
    for (int x = 1; x <= n; ++ x ) 
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            int a = id[x], b = id[y];  
            if (a != b) dout[a] ++ ;
        }
        
    int ans = 0, t = 0;
    for (int i = 1; i <= cnt; ++ i )
        if (!dout[i])
        {
            t ++ ;
            ans = sz[i];
            if (t > 1)
            {
                ans = 0;
                break;
            }
        }
        
    printf("%d\n", ans);
    return 0;
}

debug到死的一道题：
首先tp要前置++，虽然tp是时间戳的概念，但是在数组中作为下标还对应着节点编号
最后检查dout数组中，循环从1到cnt，不是从1到n，也不是从1到cnt - 1，因为cnt不是后置++，而是++完再使用
else if (st[y]) low[x] = min(low[x], dfn[y]);写歪了，写成
else if (st[y]) low[x] = min(low[x], dfn[x]);

367. 学校网络

367. 学校网络 - AcWing题库
第三章 图论 No.9有向图的强连通与半连通分量,AcWing算法提高课 课程记录,图论,深度优先,算法

将所有强连通分量缩点后，图中入度为0的点为第一问的答案
第二问是：任何一个有向无环图，需要加几条边才能使之成为一个强连通分量
结论：假设有向无环图有P个入度为0的点，Q个出度为0的点，需要加max(P, Q)个点
第三章 图论 No.9有向图的强连通与半连通分量,AcWing算法提高课 课程记录,图论,深度优先,算法

设起点的集合为P，终点的集合为Q
假设 ∣ P ∣ < = ∣ Q ∣ |P| <= |Q| ∣P∣<=∣Q∣，若 ∣ P ∣ > ∣ Q ∣ |P| > |Q| ∣P∣>∣Q∣，建个反图即可
考虑两种情况， ∣ P ∣ = 1 |P| = 1 ∣P∣=1，此时将所有的终点向起点连一条边，即 Q Q Q条边。此时从起点一定能走到所有点，从中间点一定能走到终点，而终点一定能走到起点，从而走完所有点。所以此时图中任意一点能走完图中所有点
∣ P ∣ > 1 |P| > 1 ∣P∣>1时，在终点与起点之间连一条边（尽可能与无法到达该终点的起点连线），直到起点的数量为1（每次连完边后，起点数量与终点数量都减一），此时的情况为 ∣ P ∣ = 1 |P|=1 ∣P∣=1的情况 ∣ Q ∣ − ( ∣ P ∣ − 1 ) |Q|-(|P|-1) ∣Q∣−(∣P∣−1)条边即可，由于已经连了 ∣ P ∣ − 1 |P|-1 ∣P∣−1条边，所以总共需要连的边数为 ∣ Q ∣ |Q| ∣Q∣

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110, M = N * N;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], tp, cnt;
int id[N], stk[N], tt;
bool st[N];
int din[N], dout[N];
int n, t;

void add(int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x)
{
    st[x] = true, stk[ ++ tt] = x;
    dfn[x] = low[x] = ++ tp;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (st[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int y;
        cnt ++ ;
        do {
            y = stk[tt -- ], st[y] = false;
            id[y] = cnt;
        } while (x != y);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d", &n);
    int y;
    for (int x = 1; x <= n; ++ x )
        while (scanf("%d", &y), y)
            add(x, y);
            
    for (int i = 1; i <= n; ++ i )
        if (!dfn[i])
            tarjan(i);

    
    int u = 0;
    for (int x = 1; x <= n; ++ x)
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            int a = id[x], b = id[y];
            if (a != b) din[b] ++, dout[a] ++ ;
        }
        
    int in = 0, out = 0;
    for (int i = 1; i <= cnt; ++ i )
    {
        if (!din[i]) in ++ ;
        if (!dout[i]) out ++ ;
    }
    if (cnt == 1) printf("%d\n%d\n", in, 0);
    else printf("%d\n%d\n", in, max(in, out));
    
    return 0;
}

debug：dfs的次数与缩点后入度为0的点的数量不一定相同
缩点后的图中可能存在入度和出度都为0的点，所以判断要用两个if
最后要注意，缩点后的图只有一个连通分量时，需要特判输出

1175. 最大半连通子图

1175. 最大半连通子图 - AcWing题库
第三章 图论 No.9有向图的强连通与半连通分量,AcWing算法提高课 课程记录,图论,深度优先,算法

第三章 图论 No.9有向图的强连通与半连通分量,AcWing算法提高课 课程记录,图论,深度优先,算法

首先，强连通分量一定是半连通分量，所以可以先找出图中所有强连通分量
用tarjan将图缩点，得到由强连通分量组成的有向无环图，此时再找出极大半连通分量（有向图中点最多的一条路径），可以按照拓扑序递推，找一条最长路
由于每个点都是强连通分量，计算最长路的节点数量时，需要累加所有“节点”（强连通分量）中的节点数量，只能在按照拓扑序递推最长路时，将边权设置为分量中的点数

若缩点后的两点之间存在多条边，因为导出子图一定会将和点有关的所有边选择，所以边数不同不能算不同的半连通子图，半连通分量中不存在只选择两点之间一部分边的情况，因此点数不同才算不同的半连通子图
由于我们找最长路时，需要使用边的权重，重边将影响最长路的求解，所以在建立缩点后的图时要注意给边判重
边的权重是分量中点的数量，与这些两点之间的重边没有关系，因此只需要在两点之间建立一条边

缩点建图完成后，就是递推求最长路。由于缩点的递归顺序是拓扑序的逆序，所以我们逆着遍历缩点的顺序，按照拓扑序递推求最长路即可。注意不仅要记录最长路的权值还要记录最长路的数量，分别对应最大半连通子图中点的数量以及最大半连通子图的数量

#include <iostream>
#include <cstring>
#include <unordered_set>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 2e6 + 10;
int h[N], hs[N], e[M], ne[M], idx;
int dfn[N], low[N], cnt, tp;
int stk[N], tt; bool st[N];
unordered_set<LL> s;
int sz[N], id[N];
int f[N], g[N];
int n, m, X;

void add(int h[], int x, int y)
{
    e[idx] = y, ne[idx] = h[x], h[x] = idx ++ ;
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++ tp;
    st[x] = true, stk[ ++ tt] = x;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (st[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x])
    {
        int y;
        cnt ++ ;
        do {
            y = stk[tt -- ], st[y] = false;
            id[y] = cnt;
            sz[cnt] ++ ;
        } while (x != y);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    memset(hs, -1, sizeof(hs));
    scanf("%d%d%d", &n, &m, &X);
    int x, y;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        add(h, x, y);
    }
    
    for (int i = 1; i <= n; ++ i )
        if (!dfn[i]) tarjan(i);
        
    for (int x = 1; x <= n; ++ x )
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            int a = id[x], b = id[y];
            if (a != b)
            {
                LL t = a * 100000ll + b;
                if (!s.count(t)) 
                {
                    add(hs, a, b);
                    s.insert(t);
                }
            }
        }
    for (int x = cnt; x; -- x )
    {
        if (!f[x]) f[x] = sz[x], g[x] = 1;
        for (int i = hs[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (f[y] < f[x] + sz[y])
            {
                f[y] = f[x] + sz[y];
                g[y] = g[x];
            }
            else if (f[y] == f[x] + sz[y]) 
                g[y] = (g[x] + g[y]) % X;
        }
    }
    
    int maxf = 0, sum = 0;
    for (int i = 1; i <= cnt; ++ i )
    {
        if (f[i] > maxf)
        {
            maxf = f[i];
            sum = g[i];
        }
        else if (f[i] == maxf) sum = (sum + g[i]) % X;
    }
    printf("%d\n%d\n", maxf, sum);
    return 0;
}

debug：unordered_set比set快很多，当然，也比unordered_map快
最后的最长路递推没有按照拓扑序（cnt的逆序）
没有去重，递推时要遍历缩点后的图
递推时：

if (f[y] < f[x] + sz[y])
{
	f[y] = f[x] + sz[y];
	g[y] = g[x];
}

写成了g[y] = f[x]，手滑了，但是这种错误真的超难debug

368. 银河

368. 银河 - AcWing题库
第三章 图论 No.9有向图的强连通与半连通分量,AcWing算法提高课 课程记录,图论,深度优先,算法

很直接的不等式关系，一眼差分约束，首先转换不等式关系，由于题目要求最小值，所以要用最短路，所有不等式要转换成>=的形式

  1. A >= B, B >= A
  2. B >= A + 1
  3. A >= B
  4. A >= B + 1
  5. B >= A

并且题目提供了一个边界， x i > = 1 x_i >= 1 xi​>=1，转换成 x i > = x 0 + 1 x_i >= x_0 + 1 xi​>=x0​+1
那么 x 0 x_0 x0​为虚拟源点，与所有点有一条边权为1的边，从 x 0 x_0 x0​开始遍历，一定能遍历所有的点，也一定能遍历所有的边
所以从 x 0 x_0 x0​为源点，用spfa求最长路，并且判断负环（无解）即可

这题和1169. 糖果一样，解法一样，数据一样，但是时间限制卡的很死。用sfpa求最长路与正环会超时
正解是：用线性时间复杂度的tarjan求强连通分量，判断每个强连通分量是否是正环。由于图中只有权值为0和1的边，环中权值为0是个零环，只要有一条边的权值为1，那么该强连通分量就是正环，返回无解
接着按照拓扑序求最长路即可

#include <iostream>
#include <cstring>
using namespace std;

typedef long long LL;
const int N = 1e5 + 10, M = 4e5 + 10;
int h[N], hs[N], e[M], ne[M], w[M], idx;
int dfn[N], low[N], cnt, tp;
int stk[N], tt; bool st[N];
int id[N], dis[N], sz[N];
int n, m;

void add(int h[], int x, int y, int d)
{
    e[idx] = y, ne[idx] = h[x], w[idx] = d, h[x] = idx ++ ;
}

void tarjan(int x)
{
    dfn[x] = low[x] = ++ tp;
    st[x] = true, stk[ ++ tt] = x;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!dfn[y])
        {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (st[y]) low[x] = min(low[x], dfn[y]);
    }
    if (dfn[x] == low[x]) 
    {
        int y;
        ++ cnt;
        do {
            y = stk[tt -- ], st[y] = false;
            id[y] = cnt;
            sz[cnt] ++ ;
        } while (x != y);
    }
}

int main()
{
    memset(h, -1, sizeof(h));
    memset(hs, -1, sizeof(hs));
    scanf("%d%d", &n, &m);
    int t, x, y;
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d%d", &t, &x, &y);
        if (t == 1) add(h, x, y, 0), add(h, y, x, 0);
        else if (t == 2) add(h, x, y, 1);
        else if (t == 3) add(h, y, x, 0);
        else if (t == 4) add(h, y, x, 1);
        else add(h, x, y, 0);
    }
    for (int i = 1; i <= n; ++ i ) add(h, 0, i, 1);
    for (int i = 0; i <= n; ++ i ) 
        if (!dfn[i]) tarjan(i);

    for (int x = 0; x <= n; ++ x )
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y= e[i];
            int a = id[x], b = id[y];
            if (a == b && w[i] == 1)
            {
                puts("-1");
                return 0;
            }
            else if (a != b) add(hs, a, b, w[i]);
        }
        
    for (int x = cnt; x; -- x )
    {
        for (int i = hs[x]; i != -1; i = ne[i] )
        {
            int y = e[i];
            dis[y] = max(dis[y], dis[x] + w[i]);
        }
    }
    LL sum = 0;
    for (int i = 1; i <= cnt; ++ i ) sum += (LL)sz[i] * dis[i];
    printf("%lld\n", sum);
    
    return 0;
}

debug：递推时又是没有遍历hs，缩点后的图
虚拟源点的边没有提前建，之前做sfpa时习惯在spfa里直接将所有边入队了
同时，tarjan需要遍历的点为0n之间的所有点，不是1n
最后计算总和时，连通分量乘以距离才是正解文章来源地址https://www.toymoban.com/news/detail-639174.html

到了这里，关于第三章 图论 No.9有向图的强连通与半连通分量的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • Matlab论文插图绘制模板第90期—带权重的有向图/图论图/网络图

    Matlab论文插图绘制模板第90期—带权重的有向图/图论图/网络图

    在之前的文章中，分享了Matlab 有向图 的绘制模板： 进一步，如果我们想 标注有向图的每条边的权重，或者直接用线条的粗细来表示权重 ，该怎么操作呢？ 先来看一下成品效果： 特别提示：本期内容『数据+代码』已上传资源群中，加群的朋友请自行下载。有需要的朋友可

    2024年02月16日
    浏览(40)
  • 第三章 图论 No.13拓扑排序

    第三章 图论 No.13拓扑排序

    拓扑序和DAG有向无环图联系在一起，通常用于最短/长路的线性求解 裸题：1191. 家谱树 1191. 家谱树 - AcWing题库 差分约束+拓扑排序：1192. 奖金 1192. 奖金 - AcWing题库 由于图中所有边权都是正数，可以直接使用topsort求解差分约束问题 根据题意，要求一个最小值，使用最长路求解

    2024年02月12日
    浏览(43)
  • 第三章 图论 No.12欧拉回路与欧拉路径

    第三章 图论 No.12欧拉回路与欧拉路径

    小学一笔画问题，每条边只经过一次 判断图是否存在欧拉回路：判断图是否连通（存在孤立边），再根据有向/无向具体判断 对于无向图来说， 欧拉路径 中，起点和终点的度数为奇数，中间点的度数为偶数 起点和终点：开始和结束时必须经过一条边，其余情况为：从一条边

    2024年02月12日
    浏览(41)
  • 第三章 图论 No.4最小生成树的简单应用

    第三章 图论 No.4最小生成树的简单应用

    存在边权为负的情况下，无法求最小生成树 裸题：1140. 最短网络 1140. 最短网络 - AcWing题库 套个prim的板子即可 裸题：1141. 局域网 1141. 局域网 - AcWing题库 裸题，稀疏图，套个kruskal的板子就行 需要注意的是：题目给定的图可能存在多个连通块，若使用prim算法，需要对每个连通

    2024年02月14日
    浏览(57)
  • 第三章 图论 No.10无向图的双连通分量

    第三章 图论 No.10无向图的双连通分量

    无向图有两种双连通分量 边双连通分量，e-DCC 点双连通分量，v-DCC 桥：删除这条无向边后，图变得不连通，这条边被称为桥 边双连通分量：极大的不含有桥的连通区域，说明无论删除e-DCC中的哪条边，e-DCC依旧连通 （该连通分量的任意边属于原图中的某条环）。此外，任意两

    2024年02月12日
    浏览(39)
  • 第三章 图论 No.1单源最短路及其综合应用

    第三章 图论 No.1单源最短路及其综合应用

    做乘法的最短路时，若权值=0，只能用spfa来做，相等于加法中的负权边 1129. 热浪 1129. 热浪 - AcWing题库 单源最短路，稀疏图，用堆优化Dijkstra即可，就是板子套了个背景 debug：由于是无向图，边的数量要开两倍。但是 w[N] 没改，debug了很久 所以 e[M], ne[M], w[M] ，只有 h[N] ，其他

    2024年02月14日
    浏览(46)
  • 第三章 图论 No.11二分图，匈牙利算法与点覆盖

    第三章 图论 No.11二分图，匈牙利算法与点覆盖

    257. 关押罪犯 - AcWing题库 最大最小问题，一眼二分 答案的范围在 [ 1 , 1 e 9 ] [1, 1e9] [ 1 , 1 e 9 ] 之间，二分答案，check(mid) check：将所有权值大于mid的边进行二分，若能得到二分图，返回true，否则返回false 最终将得到最优解ans，所有大于ans的边组成的图为二分图，若是图中有边

    2024年02月12日
    浏览(41)
  • 第三章 图论 No.8最近公共祖先lca, tarjan与次小生成树

    第三章 图论 No.8最近公共祖先lca, tarjan与次小生成树

    O ( m l o g n ) O(mlogn) O ( m l o g n ) ，n为节点数量，m为询问次数，lca是一种在线处理询问的算法 自己也是自己的祖先 倍增： f a ( i , j ) fa(i, j) f a ( i , j ) 表示从i开始，向上走 2 j 2^j 2 j 步走到的点 j = 0，走到父节点 j 0，分两步走，先走到 2 j − 1 2^{j-1} 2 j − 1 步再走 2 j − 1 2^{

    2024年02月13日
    浏览(43)
  • 第三章 图论 No.6负环之01分数规划与特殊建图方式

    第三章 图论 No.6负环之01分数规划与特殊建图方式

    裸题：904. 虫洞 904. 虫洞 - AcWing题库 这个==真的服，调半天，还有，邻接表的大小又设置错了 01分数规划：361. 观光奶牛 361. 观光奶牛 - AcWing题库 在图论问题中，所有形如：某个部分之和除以某个部分之和最大的问题，被称为01分数规划，通常使用二分解决这类问题 根据题意

    2024年02月13日
    浏览(41)
  • 第三章 图论 No.5最小生成树之虚拟源点，完全图与次小生成树

    第三章 图论 No.5最小生成树之虚拟源点，完全图与次小生成树

    虚拟源点：1146. 新的开始 1146. 新的开始 - AcWing题库 与一般的最小生成树问题不同，本题需要在建立电站的电井之间建立电网，在两个电站之间建立电网需要花费金额，可以看成一条具有权值的边 但是建立电网的前提是：其中一个电井需要建立电站，建立电站也需要费用 已经

    2024年02月14日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包