国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<td id="lpiem"></td>

第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹

2年前作者：.SacaJawea分類：Toy博客閱讀(26)違法舉報

這篇具有很好參考價值的文章主要介紹了第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹,AcWing算法提高課課程記錄,圖論,算法

lca

$O (m l o g n)$ ，n為節(jié)點數量，m為詢問次數，lca是一種在線處理詢問的算法
自己也是自己的祖先

倍增：
$f a (i, j)$ 表示從i開始，向上走 $2^j$ 步走到的點
j = 0，走到父節(jié)點
j > 0，分兩步走，先走到 $2^{j-1}$ 步再走 $2^{j-1}$ 步，那么一共就會走 $2^j$ 步， $f a (i, j) = f a (f a (i, j ? 1), j ? 1)$
$d e pt h (i)$ 表示層數

將兩點跳到同一層
讓兩個點同時往上跳，直到跳到公共祖先的下一層

第一步：基于二進制的思想，x和y之間的層數差距為 $d e pt h (x) ? d e pt h (y)$ ，假設y的層數小于x的層數，此時x要往上跳
若要跳k層，那么根據k的二進制表示將k拆分成多個2的冪相加，由于我們已經預處理了 $f (i, j)$ ，所以根據 $f (i, j)$ 的值往上跳即可
當 $f (x, k) = f (y, k)$ 時，即x往上跳k步和y往上跳k步后，位于同一個位置，此時找到了一個公共祖先，但不是最近公共祖先，所以這里要減小k的值，直到 $f (x, k) \neq = f (y, k)$ ，此時才找到了最近公共祖先

規(guī)定 $d e pt h (0) = 0$ ，0號點為哨兵，位于第0層，根節(jié)點位于第一層
向上跳 $2^k$ 步后，若跳出了這顆樹，那么 $f (i, k) = 0$

第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹,AcWing算法提高課課程記錄,圖論,算法

預處理depth和fa的板子：

void bfs(int root)
{
	memset(dis, 0x3f, sizeof(dis));
	q[tt ++ ] = root;
	depth[root] = 1, depth[0] = 0;
	while (tt >= hh)
	{
		int x = q[hh ++ ];
		for (int i = h[x]; i != -1; i = ne[i])
		{
			int y = e[i];
			if (depth[y] > depth[x] + 1)
			{
				depth[y] = depth[x] + 1;
				q[tt ++ ] = y;
				fa[y][0] = x;
				for (int k = 1; k <= c; ++ k )
					fa[y][k] = fa[fa[y][k - 1]][k - 1];
			}
		}
	}
}

lca板子：

int lca(int x, int y)
{
	if (depth[x] < depth[y]) swap(x, y);
	for (int k = c; k >= 0; -- k )
		if (depth[fa[x][k]] >= depth[y])
			x = fa[x][k];
	if (x == y) return y;
	for (int k = c; k >= 0; -- k )
		if (fa[x][k] != fa[y][k])
		{
			x = fa[x][k];
			y = fa[x][k];
		}
	return fa[x][0];
}

Tarjan

$O (n + m)$ ，n為節(jié)點數量，m為詢問次數
tarjan是一種離線處理詢問的算法，是向上標記法的優(yōu)化
在深度優(yōu)先遍歷時，將所有點分成三大類

已經遍歷過且已經回溯的點
已經遍歷但正在搜索的分支
還未搜索到的點

第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹,AcWing算法提高課課程記錄,圖論,算法
將已經遍歷且回溯的點標記成2，正在遍歷的點標記成1，未遍歷的點標記成0
對于正在回溯的點，需要處理所有有關該點的詢問信息：若詢問的另外一個點已經遍歷過（回溯完成），那么該點將被分到一個集合中，集合的代表點就是兩點的最近公共祖先
比如上圖，當前正在遍歷x這個點，已經遍歷完的點為綠色部分，這些點所屬集合的代表點位于紅色分支上

模板：

// 用dfs維護dis數組
void dfs(int x, int fa)
{
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int y = e[i];
		if (y != fa)
		{
			dis[y] = dis[x] + w[i];
			dfs(y, x);
		}
	}
}

// tarjan處理詢問
void tarjan(int x)
{
	st[x] = 1; // 當前正在遍歷該點
	for (int i = h[x]; i != -1; i = ne[i])
	{
		int y = e[i];
		if (!st[y]) // 當前為遍歷ydian
		{
			tarjan(y);
			p[y] = u;
		}
	}
	for (auto item : query[x]) // 處理有關當前節(jié)點的詢問
	{
		int y = item.first, id = item.first; // id為該詢問的唯一編號
		if (st[y] == 2) // 詢問的另一點已經遍歷過
		{
			int anc = find(y); // 找到集合的代表點，公共祖先
			res[id] = dis[x] + dis[y] - 2 * dis[anc]; // 根據id將答案存儲到數組中
		}
	}
	st[x] = 2; // 當前節(jié)點遍歷完
}

板子題：1172. 祖孫詢問

1172. 祖孫詢問 - AcWing題庫
第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹,AcWing算法提高課課程記錄,圖論,算法

由于樹的層數最大有40000層，所以一個節(jié)點最多向上跳 $l o g 400000$ 層，大概是一個大于 $2^{15}$ 小于 $2^{16}$ 的數，所以最多跳 $2^{16} - 1$ 層，二進制位取15即可

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

const int N = 4e4 + 10, M = 2 * N;
int h[N], e[M], ne[M], idx;
int q[N], hh, tt = -1;
int depth[N], fa[N][16]; // 最多跳2^16-1
int n;

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

void bfs(int root)
{
    q[++ tt] = root;
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[root] = 1;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (depth[y] > depth[x] + 1)
            {
                depth[y] = depth[x] + 1;
                fa[y][0] = x;
                q[++ tt ] = y;
                for (int k = 1; k <= 15; ++ k )
                    fa[y][k] = fa[fa[y][k - 1]][k - 1];
            }
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 15; k >= 0; -- k )
        if (depth[fa[x][k]] >= depth[y])
            x = fa[x][k];
    if (x == y) return y;
    for (int k = 15; k >= 0; -- k )
        if (fa[x][k] != fa[y][k])
        {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0];
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d", &n);
    int root;
    int a, b;
    for (int i = 0; i < n; ++ i )
    {
        scanf("%d%d", &a, &b);
        if (b == -1) root = a;
        else add(a, b), add(b, a);
    }
    
    bfs(root);
    int m;
    scanf("%d", &m);
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &a, &b);
        int t = lca(a, b);
        if (t == a) puts("1");
        else if (t == b) puts("2");
        else puts("0");
    }
    return 0;
}

lca或tarjan：1171. 距離

1171. 距離 - AcWing題庫
第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹,AcWing算法提高課課程記錄,圖論,算法

與上題一樣，題目要處理很多詢問，可以用lca或者離線tarjan解決
樹的最短路問題可以從公共祖先的角度考慮，假設x和y的公共祖先為t， $d i s (t)$ 為根節(jié)點到t的距離，那么x和y之間的最短距離就是 $d i s (x) + d i s (y) ? 2 ? d i s (t)$

題目沒有給定根節(jié)點，我們任意指定一個點為根節(jié)點即可

lca解法：

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

const int N = 1e4 + 10, M = 2 * N;
int h[N], e[M], ne[M], w[M], idx;
int depth[N], fa[N][16];
int q[N], hh, tt = -1;
int dis[N];

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

void dfs(int root)
{
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[root] = 1;
    q[++ tt ] = root;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (depth[y] > depth[x] + 1)
            {
                depth[y] = depth[x] + 1;
                dis[y] = dis[x] + w[i];
                fa[y][0] = x;
                q[++ tt ] = y;
                for (int k = 1; k <= 15; ++ k )
                    fa[y][k] = fa[fa[y][k - 1]][k - 1];
            }
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 15; k >= 0; -- k )
        if (depth[fa[x][k]] >= depth[y])
            x = fa[x][k];
    if (x == y) return y;
    for (int k = 15; k >= 0; -- k )
        if (fa[x][k] != fa[y][k])
        {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0];
}

int main()
{
    memset(h, -1, sizeof(h));
    int n, m;
    scanf("%d%d", &n, &m);
    int x, y, d;
    for (int i = 0; i < n - 1; ++ i )
    {
        scanf("%d%d%d", &x, &y, &d);
        add(x, y, d), add(y, x, d);
    }
    dfs(1);
    
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        int t = lca(x, y);
        printf("%d\n", dis[x] + dis[y] - 2 * dis[t]);
    }
    return 0;
}

tarjan解法：

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

const int N = 1e4 + 10, M = 2 * N;
typedef pair<int, int> PII;
vector<PII> query[N];
int h[N], e[M], ne[M], w[M], idx;
int res[M], dis[N], st[N], p[N];
int n, m;

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

void dfs(int x, int fa)
{
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (y != fa)
        {
            dis[y] = dis[x] + w[i];
            dfs(y, x);
        }
    }
}

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

void tarjan(int x)
{
    st[x] = 1;
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (!st[y])
        {
            tarjan(y);
            p[y] = x;
        }
    }
    
    for (auto item : query[x])
    {
        int y = item.first, id = item.second;
        if (st[y] == 2)
        {
            int anc = find(y);
            res[id] = dis[x] + dis[y] - 2 * dis[anc];
        }
    }
    st[x] = 2;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y, d;
    for (int i = 0; i < n - 1; ++ i )
    {
        scanf("%d%d%d", &x, &y, &d);
        add(x, y, d), add(y, x, d);
    }
    for (int i = 0; i < m; ++ i )
    {
        scanf("%d%d", &x, &y);
        query[x].push_back({y, i}); // 將查詢的另一個點與查詢編號保存
        query[y].push_back({x, i});
    }
    
    dfs(1, -1);
    for (int i = 1; i <= n; ++ i ) p[i] = i;
    tarjan(1);
    for (int i = 0; i < m; ++ i ) printf("%d\n", res[i]);
    
    return 0;
}

debug：維護的query信息要不同地插入兩次

query[x].push_back({y, i});
query[y].push_back({x, i});

因為當前詢問有關x的信息時，y可能沒有遍歷完，但是詢問y有關的信息時，x是遍歷完的

356. 次小生成樹

356. 次小生成樹 - AcWing題庫
第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹,AcWing算法提高課課程記錄,圖論,算法

$d 1 (i, j)$ 表示從i往上跳 $2^j$ 層后，路徑上的最大邊權
$d 2 (i, j)$ 表示從i往上跳 $2^j$ 層后，路徑上的次大邊權
跳 $2^j$ 步是一個類似分治的過程，分成兩部分跳，這兩部分依舊能分成兩部分跳
路徑上的最大值為每一段的最大值取max，次大值為所有子路徑的最大值和次大值中的第二大，每次遍歷子線段時維護信息即可

if (d > d1) d2 = d1, d1 = d; 
else if (d != d1 && d > d2) d2 = d;

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

typedef long long LL;
const int N = 1e5 + 10, M = 3e5 + 10, INF = 0x3f3f3f3f;
struct Edge
{
    int x, y, w;
    bool f;
    bool operator<(const Edge& e) const 
    {
        return w < e.w;
    }
}edges[M];

int h[N], e[M], ne[M], w[M], idx;
int p[N], depth[N], fa[N][17];
int q[N], hh, tt = -1;
int d1[N][17], d2[N][17];
int d[M];
int n, m;

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

int find(int x)
{
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}

LL kruskal()
{
    LL res = 0;
    sort(edges, edges + m);
    for (int i = 1; i <= n; ++ i ) p[i] = i;
    for (int i = 0; i < m; ++ i )
    {
        auto t = edges[i];
        int x = t.x, y = t.y, w = t.w;
        int px = find(x), py = find(y);
        if (px != py)
        {
            res += w;
            p[px] = py;
            edges[i].f = true;
            add(x, y, w), add(y, x, w);
        }
    }
    return res;
}

void bfs()
{
    q[++ tt ] = 1;
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[1] = 1;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (depth[y] > depth[x] + 1)
            {
                depth[y] = depth[x] + 1;
                fa[y][0] = x;
                d1[y][0] = w[i], d2[y][0] = -INF;
                q[++ tt ] = y;
                for (int k = 1; k <= 16; ++ k )
                {
                    int mid = fa[y][k - 1];
                    fa[y][k] = fa[mid][k - 1];
                    d1[y][k] = d2[y][k] = -INF;
                    int a[4] = { d1[mid][k - 1], d2[mid][k - 1], d1[y][k - 1], d2[y][k - 1] };
                    for (int i = 0; i < 4; ++ i )
                    {
                        if (a[i] > d1[y][k]) d2[y][k] = d1[y][k], d1[y][k] = a[i];
                        else if (a[i] != d1[y][k] && a[i] > d2[y][k]) d2[y][k] = a[i];
                    }
                }
            }
        }
    }
}


int lca(int x, int y, int w)
{
    int cnt = 0;
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 16; k >= 0; -- k )
        if (depth[fa[x][k]] >= depth[y])
        {
            d[cnt ++ ] = d1[x][k];
            d[cnt ++ ] = d2[x][k];
            x = fa[x][k];
        }
    if (x != y)
    {
        for (int k = 16; k >= 0; -- k )
        {
            if (fa[x][k] != fa[y][k])
            {
                d[cnt ++ ] = d1[x][k], d[cnt ++ ] = d2[x][k];
                d[cnt ++ ] = d1[y][k], d[cnt ++ ] = d2[y][k];
                x = fa[x][k], y = fa[y][k];
            }
            d[cnt ++ ] = d1[x][0], d[cnt ++ ] = d2[x][0];
            d[cnt ++ ] = d1[y][0], d[cnt ++ ] = d2[y][0];
        }
    }
    int dmax1 = -INF, dmax2 = -INF;
    for (int i = 0; i < cnt; ++ i )
    {
        if (d[i] > dmax1) dmax2 = dmax1, dmax1 = d[i];
        else if (d[i] != dmax1 && d[i] > dmax2) dmax2 = d[i];
    }
    
    if (w > dmax1) return w - dmax1;
    return w - dmax2;
}


int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++ i )
        scanf("%d%d%d", &edges[i].x, &edges[i].y, &edges[i].w);
        
    LL sum = kruskal(); // 最小生成樹的權值
    bfs();
    
    LL res = 1e19;
    for (int i = 0; i < m; ++ i )
        if (!edges[i].f)
            res = min(res, sum + lca(edges[i].x, edges[i].y, edges[i].w));
    
    printf("%lld\n", res);
    return 0;
}

352. 闇の連鎖

352. 闇の連鎖 - AcWing題庫
第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹,AcWing算法提高課課程記錄,圖論,算法

第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹,AcWing算法提高課課程記錄,圖論,算法

樹上差分，將x到y(tǒng)的最短路徑上所有的邊加上c，若p為x和y的公共祖先，那么
d(x) += c, d(y) += c, d(p) -= 2c
如何計算某條邊的權值？以這條邊的子節(jié)點為根的子樹中，所有邊的權值相加為這條邊的權值

在一顆樹中，刪除任意一條邊，那么這顆樹將被切成兩個連通塊
若向樹中再添加一條邊，那么這條非樹邊和樹邊就一定構成環(huán)，要向將此時的“樹”切成兩個連通塊，就要刪除環(huán)中的任意一條樹邊與這條非樹邊
題目限制只能先切樹邊，再切非樹邊，一共兩次，兩次過后還沒有切成兩個連通塊，說明這個方案行不通
當切除樹邊，不用再切除非樹邊就得到兩個連通塊時，由于題目限制，還需要切除一條非樹邊，假設非樹邊有m條，那么此時可以選擇m條邊中的任意一條切除，此時的方案數為m
若切除樹邊后，還要再切除一條非樹邊，才能得到兩個連通塊時，此時的方案數為1，只能切除這條環(huán)中的非樹邊
若切除樹邊后，還要再切除大于一條的非樹邊，此時無法再切除，方案數為0

現在的問題是，如何知道切除某條樹邊后，還需要再切除幾條非樹邊？
假設現在已經用樹邊建立了一棵樹，此時再添加非樹邊將構成環(huán)，將環(huán)中的所有樹邊權值加1，假設初始權值為0，此時可以使用樹上差分
然后遍歷所有的樹邊，根據邊權計算方案數文章來源地址http://www.zghlxwxcb.cn/news/detail-643252.html

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

const int N = 1e5 + 10, M = 2e5 + 10;
int h[N], e[M], ne[M], idx;
int depth[N], fa[N][17];
int q[N], hh, tt = -1;
int d[N];
int n, m, ans;

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

void bfs()
{
    memset(depth, 0x3f, sizeof(depth));
    depth[0] = 0, depth[1] = 1;
    q[++ tt ] = 1;
    while (tt >= hh)
    {
        int x = q[hh ++ ];
        for (int i = h[x]; i != -1; i = ne[i])
        {
            int y = e[i];
            if (depth[y] > depth[x] + 1)
            {
                depth[y] = depth[x] + 1;
                fa[y][0] = x;
                q[++ tt ] = y;
                for (int k = 1; k <= 16; ++ k )
                    fa[y][k] = fa[fa[y][k - 1]][k - 1];
            }
        }
    }
}

int lca(int x, int y)
{
    if (depth[x] < depth[y]) swap(x, y);
    for (int k = 16; k >= 0; -- k )
        if (depth[fa[x][k]] >= depth[y])
            x = fa[x][k];
    if (x == y) return x;
    for (int k = 16; k >= 0; -- k )
        if (fa[x][k] != fa[y][k])
        {
            x = fa[x][k];
            y = fa[y][k];
        }
    return fa[x][0];
}

int dfs(int x, int f)
{
    int res = d[x];
    for (int i = h[x]; i != -1; i = ne[i])
    {
        int y = e[i];
        if (f != y)
        {
            int t = dfs(y, x);
            if (t == 0) ans += m;
            else if (t == 1) ans ++;
            res += t;
        }
    }
    return res;
}

int main()
{
    memset(h, -1, sizeof(h));
    scanf("%d%d", &n, &m);
    int x, y;
    for (int i = 0; i < n - 1; ++ i )
    {        
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    
    bfs();
    int res = 0;
    for (int i = 0; i < m; ++ i)
    {
        scanf("%d%d", &x, &y);
        int p = lca(x, y);
        d[x] ++, d[y] ++, d[p] -= 2;
    }
    dfs(1, -1);
    printf("%d\n", ans);
    return 0;
}

到了這里，關于第三章圖論 No.8最近公共祖先lca, tarjan與次小生成樹的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。如若轉載，請注明出處：如若內容造成侵權/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經查實，立即刪除！

分享到：

領支付寶紅包贊助服務器費用

第三章圖論 No.12歐拉回路與歐拉路徑
小學一筆畫問題，每條邊只經過一次判斷圖是否存在歐拉回路：判斷圖是否連通（存在孤立邊），再根據有向/無向具體判斷對于無向圖來說，歐拉路徑中，起點和終點的度數為奇數，中間點的度數為偶數起點和終點：開始和結束時必須經過一條邊，其余情況為：從一條邊
2024年02月12日
瀏覽(23)
第三章圖論 No.1單源最短路及其綜合應用
做乘法的最短路時，若權值=0，只能用spfa來做，相等于加法中的負權邊 1129. 熱浪 1129. 熱浪 - AcWing題庫單源最短路，稀疏圖，用堆優(yōu)化Dijkstra即可，就是板子套了個背景 debug：由于是無向圖，邊的數量要開兩倍。但是 w[N] 沒改，debug了很久所以 e[M], ne[M], w[M] ，只有 h[N] ，其他
2024年02月14日
瀏覽(21)
第三章圖論 No.10無向圖的雙連通分量
無向圖有兩種雙連通分量邊雙連通分量，e-DCC 點雙連通分量，v-DCC 橋：刪除這條無向邊后，圖變得不連通，這條邊被稱為橋邊雙連通分量：極大的不含有橋的連通區(qū)域，說明無論刪除e-DCC中的哪條邊，e-DCC依舊連通（該連通分量的任意邊屬于原圖中的某條環(huán)）。此外，任意兩
2024年02月12日
瀏覽(16)
第三章圖論 No.4最小生成樹的簡單應用
存在邊權為負的情況下，無法求最小生成樹裸題：1140. 最短網絡 1140. 最短網絡 - AcWing題庫套個prim的板子即可裸題：1141. 局域網 1141. 局域網 - AcWing題庫裸題，稀疏圖，套個kruskal的板子就行需要注意的是：題目給定的圖可能存在多個連通塊，若使用prim算法，需要對每個連通
2024年02月14日
瀏覽(31)
第三章圖論 No.11二分圖，匈牙利算法與點覆蓋
257. 關押罪犯 - AcWing題庫最大最小問題，一眼二分答案的范圍在 [ 1 , 1 e 9 ] [1, 1e9] [ 1 , 1 e 9 ] 之間，二分答案，check(mid) check：將所有權值大于mid的邊進行二分，若能得到二分圖，返回true，否則返回false 最終將得到最優(yōu)解ans，所有大于ans的邊組成的圖為二分圖，若是圖中有邊
2024年02月12日
瀏覽(19)
第三章圖論 No.6負環(huán)之01分數規(guī)劃與特殊建圖方式
裸題：904. 蟲洞 904. 蟲洞 - AcWing題庫這個==真的服，調半天，還有，鄰接表的大小又設置錯了 01分數規(guī)劃：361. 觀光奶牛 361. 觀光奶牛 - AcWing題庫在圖論問題中，所有形如：某個部分之和除以某個部分之和最大的問題，被稱為01分數規(guī)劃，通常使用二分解決這類問題根據題意
2024年02月13日
瀏覽(19)
第三章圖論 No.9有向圖的強連通與半連通分量
連通分量是無向圖的概念，yxc說錯了，不要被誤導強連通分量：在一個有向圖中，對于分量中的任意兩點u，v，一定能從u走到v，且能從v走到u。強連通分量是一些點的集合，若加入其他點，強連通分量中的任意兩點就不能互相遞達半連通分量：在一個有向圖中，對于分量中
2024年02月13日
瀏覽(17)
第三章圖論 No.5最小生成樹之虛擬源點，完全圖與次小生成樹
虛擬源點：1146. 新的開始 1146. 新的開始 - AcWing題庫與一般的最小生成樹問題不同，本題需要在建立電站的電井之間建立電網，在兩個電站之間建立電網需要花費金額，可以看成一條具有權值的邊但是建立電網的前提是：其中一個電井需要建立電站，建立電站也需要費用已經
2024年02月14日
瀏覽(24)
第三章圖論 No.3 flody之多源匯最短路，傳遞閉包，最小環(huán)與倍增
flody的四個應用：多源匯最短路傳遞閉包找最小環(huán) 恰好經過k條邊的最短路倍增多源匯最短路：1125. 牛的旅行 1125. 牛的旅行 - AcWing題庫直徑概念：同一連通塊中，兩個距離最遠的點之間的距離如何求直徑？由于圖中存在著兩個連通塊，所以直接對全圖做一個flody，就能更
2024年02月14日
瀏覽(27)
《圖》經典題題解（拓撲排序，DFS，BFS，Floyd,Dijkstra,LCA最近公共祖先，最小生成樹，最短路徑）（ACM）
目錄拓撲排序 / 家譜樹 p1359租用潛艇 P1938[USACO09NOV] Job Hunt S? 最短路計數 797. 所有可能的路徑? 200.島嶼數量 DFS BFS 695.島嶼的最大面積 DFS BFS P1119 災后重建? P1629 郵遞員送信法一：Floyd 法二：Dijkstra P3379 【模板】最近公共祖先（LCA）最小生成樹法一：prim算法法二：Kruskal算
2024年04月14日
瀏覽(19)

<tr id="2wpfo"></tr>

^{<legend id="2wpfo"></legend>}^{<tr id="2wpfo"></tr>}