【图论】 【割点】 【双连通分类】LCP 54. 夺回据点

本文涉及知识点

图论 割点 双连通分类
割点原理及封装好的割点类

LeetCode LCP 54. 夺回据点

魔物了占领若干据点,这些据点被若干条道路相连接,roads[i] = [x, y] 表示编号 x、y 的两个据点通过一条道路连接。
现在勇者要将按照以下原则将这些据点逐一夺回:
在开始的时候,勇者可以花费资源先夺回一些据点,初始夺回第 j 个据点所需消耗的资源数量为 cost[j]
接下来,勇者在不消耗资源情况下,每次可以夺回一个和「已夺回据点」相连接的魔物据点,并对其进行夺回
注:为了防止魔物暴动,勇者在每一次夺回据点后(包括花费资源夺回据点后),需要保证剩余的所有魔物据点之间是相连通的(不经过「已夺回据点」)。
请返回勇者夺回所有据点需要消耗的最少资源数量。
注意:
输入保证初始所有据点都是连通的,且不存在重边和自环
示例 1:
输入: cost = [1,2,3,4,5,6] roads = [[0,1],[0,2],[1,3],[2,3],[1,2],[2,4],[2,5]]
输出:6
解释: 勇者消耗资源 6 夺回据点 0 和 4,魔物据点 1、2、3、5 相连通; 第一次夺回据点 1,魔物据点 2、3、5 相连通; 第二次夺回据点 3,魔物据点 2、5 相连通; 第三次夺回据点 2,剩余魔物据点 5; 第四次夺回据点 5,无剩余魔物据点; 因此最少需要消耗资源为 6,可占领所有据点。i
在这里插入图片描述

示例 2:

输入: cost = [3,2,1,4] roads = [[0,2],[2,3],[3,1]]
在这里插入图片描述

输出:2

解释: 勇者消耗资源 2 夺回据点 1,魔物据点 0、2、3 相连通; 第一次夺回据点 3,魔物据点 2、0 相连通; 第二次夺回据点 2,剩余魔物据点 0; 第三次夺回据点 0,无剩余魔物据点; 因此最少需要消耗资源为 2,可占领所有据点。image.png

提示:
1 <= roads.length, cost.length <= 105
0 <= roads[i][0], roads[i][1] < cost.length
1 <= cost[i] <= 109

预备知识

点双连通:删掉任意一个点之后及关联的边后,图仍联通。
点双连通分量的缩点

性质一: 无向图中,要么是树边,父亲指向孩子;要么是回边,后代指向祖宗。见:割点原理及封装好的割点类。
性质二:一个环一定是点双连通。
性质三:一个环+一个树,一定不是点双连通区域。令树的一边a,b不在环上,b不在环上。则删除a,b就成了新的连通区域。
性质四:两个环有一个点重合,一定不是点双连通。删除重合点就分开了。
性质五:两个环有两个或更多的顶点相同,则一定是双连通区域。令相同的顶点是a和b。删除a后,两个环余下的点,通过b连通。删除b,类似。
性质六:设G1,G2最大点双连通图,如果G1和G2包括相同的边ab,则G1 == G2。删除a后,G1和G2所有的点都可以通过b连通,故G1和G2可以合并。
性质七:无向图的任何树边都只属于一个强连通分量。

简化情况

假定是树,且节点数大于等于3。一定会存在度数>=2的节点,以任意度数为2的根,形成树。
令叶子数是k,选择k-2个叶子结束,无法完全占据。2个叶子节点最近公共祖先无法消除。
选择k-1个叶子,一定可以占据。设没选择的节点是a,k-1个消除到和a的公共祖先,余下的树都是a的祖先,从根开始消除。
不能选择根节点,除一个子树外,可以选择排除一个叶子节 点外的叶子节点;其它子树要全部选择。显然劣于k-1叶子节点。
不能选择枝节点,选了只有两个选择:
a,本子树全选,本子树外的叶子排除一个外全选。
b,本子树外的节点全选。本子树的叶子排除一个外全选。
显然劣于选择k-1个叶子节点。

在这里插入图片描述
红色字体是割点,红色线段是回边。
共四个点双连通区域,红色背景(节点0)、绿色背景(3)、紫色背景(6) 只和一个割点连接,消除不会形成新的连通区域。蓝色节点(4)和两个割点连通,首先删除会,让2和5断开。

点双连通区域占据任意点,任意剩余据点也是连通。

关于点双连通区域

性质一:除根节点外的任何节点x都会放到符合以下条件的next所在连通区域。
next就是x或next是x的祖宗。如果多个next,取级别最高的。
断开cur后,next和cur的祖宗不连通。每个节点只会入栈出栈一次。
性质二:next的父节点也会放到next所在的双连通区域。
性质三:除根节点外的任何节点x 都有符合性质一的next,根节点的子节点一定符合。

代码

两种特殊情况: 一个连通区域只有一个点。本类会解析错误,解析成没有点双连同区域。
没有割点,会解析成一个点双连通区域,解析正确。本题要特殊处理。

class CNeiBo
{
public:	
	static vector<vector<int>> Two(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0) 
	{
		vector<vector<int>>  vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase);
			}
		}
		return vNeiBo;
	}	
	static vector<vector<std::pair<int, int>>> Three(int n, vector<vector<int>>& edges, bool bDirect, int iBase = 0)
	{
		vector<vector<std::pair<int, int>>> vNeiBo(n);
		for (const auto& v : edges)
		{
			vNeiBo[v[0] - iBase].emplace_back(v[1] - iBase, v[2]);
			if (!bDirect)
			{
				vNeiBo[v[1] - iBase].emplace_back(v[0] - iBase, v[2]);
			}
		}
		return vNeiBo;
	}
	static vector<vector<int>> Grid(int rCount, int cCount, std::function<bool(int, int)> funVilidCur, std::function<bool(int, int)> funVilidNext)
	{
		vector<vector<int>> vNeiBo(rCount * cCount);
		auto Move = [&](int preR, int preC, int r, int c)
		{
			if ((r < 0) || (r >= rCount))
			{
				return;
			}
			if ((c < 0) || (c >= cCount))

			{
				return;
			}
			if (funVilidCur(preR, preC) && funVilidNext(r, c))
			{
				vNeiBo[cCount * preR + preC].emplace_back(r * cCount + c);
			}
		};

		for (int r = 0; r < rCount; r++)
		{
			for (int c = 0; c < cCount; c++)
			{
				Move(r, c, r + 1, c);
				Move(r, c, r - 1, c);
				Move(r, c, r, c + 1);
				Move(r, c, r, c - 1);
			}
		}
		return vNeiBo;
	}
};

//割点
class CCutPoint
{
public:
	CCutPoint(const vector<vector<int>>& vNeiB) : m_iSize(vNeiB.size())
	{
		m_vNodeToTime.assign(m_iSize, -1);
		m_vCutNewRegion.resize(m_iSize);		
	}
	void Init(const vector<vector<int>>& vNeiB)
	{
		for (int i = 0; i < m_iSize; i++)
		{
			if (-1 == m_vNodeToTime[i])
			{
				m_vRegionFirstTime.emplace_back(m_iTime);
				dfs(vNeiB, i, -1);
			}
		}
	}	
	const int m_iSize;
	const vector<int>& Time()const { return m_vNodeToTime; }//各节点的时间戳
	const vector<int>& RegionFirstTime()const { return m_vRegionFirstTime; }//各连通区域的最小时间戳
	vector<bool> Cut()const { 
		vector<bool> ret;
		for (int i = 0; i < m_iSize; i++)
		{
			ret.emplace_back(m_vCutNewRegion[i].size());
		}
		return ret; }//
	const vector < vector<pair<int, int>>>& NewRegion()const { return m_vCutNewRegion; };
protected:
	int dfs(const vector<vector<int>>& vNeiB, const int cur, const int parent)
	{
		int iMinTime = m_vNodeToTime[cur] = m_iTime++;
		OnBeginDFS(cur);
		int iRegionCount = (-1 != parent);//根连通区域数量
		for (const auto& next : vNeiB[cur]) {
			if (-1 != m_vNodeToTime[next]) {
				iMinTime = min(iMinTime, m_vNodeToTime[next]);
				continue;
			}
			const int childMinTime = dfs(vNeiB, next, cur);
			iMinTime = min(iMinTime, childMinTime);
			if (childMinTime >= m_vNodeToTime[cur]) {
				iRegionCount++;
				m_vCutNewRegion[cur].emplace_back(m_vNodeToTime[next], m_iTime);
				OnNewRegion(cur, next);
			}
		}
		if (iRegionCount < 2)
		{
			m_vCutNewRegion[cur].clear();
		}
		return iMinTime;
	}
	virtual void OnNewRegion(int cur, int next) {};
	virtual void OnBeginDFS(int cur) {};
	vector<int> m_vNodeToTime;
	vector<int> m_vRegionFirstTime;
	vector < vector<pair<int, int>>> m_vCutNewRegion; //m_vCutNewRegion[c]如果存在[left,r) 表示割掉c后,时间戳[left,r)的节点会形成新区域
	int m_iTime = 0;
};

class CConnectAfterCutPoint 
{
public:
	CConnectAfterCutPoint(const vector<vector<int>>& vNeiB) :m_ct(vNeiB)
	{
		m_vTimeToNode.resize(m_ct.m_iSize);
		m_vNodeToRegion.resize(m_ct.m_iSize);
		for (int iNode = 0; iNode < m_ct.m_iSize; iNode++)
		{
			m_vTimeToNode[m_ct.Time()[iNode]] = iNode;
		}
		for (int iTime = 0,iRegion= 0; iTime < m_ct.m_iSize; iTime++)
		{
			if ((iRegion < m_ct.RegionFirstTime().size()) && (m_ct.RegionFirstTime()[iRegion] == iTime))
			{
				iRegion++;
			}
			m_vNodeToRegion[m_vTimeToNode[iTime]] = (iRegion - 1);
		}
	}
	bool Connect(int src, int dest, int iCut)const
	{
		if (m_vNodeToRegion[src] != m_vNodeToRegion[dest])
		{
			return false;//不在一个连通区域
		}
		if (0 == m_ct.NewRegion()[iCut].size())
		{//不是割点
			return true;
		}
		const int r1 = GetCutRegion(iCut, src);
		const int r2 = GetCutRegion(iCut, dest);
		return r1 == r2;
	}
	vector<vector<int>> GetSubRegionOfCut(const int iCut)const
	{//删除iCut及和它相连的边后,iCut所在的区域会分成几个区域:父节点一个区域、各子节点		一个区域
			//父节点所在区域可能为空,如果iCut所在的连通区域只有一个节点,则返回一个没有节点的			区域。
		const auto& v = m_ct.NewRegion()[iCut];
		vector<int> vParen;
		const int iRegion = m_vNodeToRegion[iCut];
		const int iEndTime = (iRegion + 1 == m_ct.RegionFirstTime().size()) ? m_ct.m_iSize : m_ct.RegionFirstTime()[iRegion+1];
		vector<vector<int>> vRet;	
		for (int iTime = m_ct.RegionFirstTime()[iRegion],j=-1; iTime < iEndTime; iTime++)
		{
			if (iCut == m_vTimeToNode[iTime])
			{
				continue;
			}
			if ((j + 1 < v.size()) && (v[j + 1].first == iTime))
			{
				j++;
				vRet.emplace_back();
			}
			const int iNode = m_vTimeToNode[iTime];
			if ((-1 != j ) && (iTime >= v[j].first) && (iTime < v[j].second))
			{
				vRet.back().emplace_back(iNode);
			}
			else
			{
				vParen.emplace_back(iNode);
			}			
		}
		vRet.emplace_back();
		vRet.back().swap(vParen);
		return vRet;
	}	
protected:
	int GetCutRegion(int iCut, int iNode)const
	{
		const auto& v = m_ct.NewRegion()[iCut];
		auto it = std::upper_bound(v.begin(), v.end(), m_ct.Time()[iNode], [](int time, const std::pair<int, int>& pr) {return  time < pr.first; });
		if (v.begin() == it)
		{
			return v.size();
		}
		--it;
		return (it->second > m_ct.Time()[iNode]) ? (it - v.begin()) : v.size();
	}
	vector<int> m_vTimeToNode;
	vector<int> m_vNodeToRegion;//各节点所在区域
	const CCutPoint m_ct;
};

class CPointBitConnect :public CCutPoint
{//点双连通区域
public:
	CPointBitConnect(const vector<vector<int>>& vNeiB):CCutPoint(vNeiB)
	{
		
	}
	stack<int> m_staNodes;
	vector<vector<int>> m_vBitConnect;
protected:
	virtual void OnNewRegion(int cur, int next) override {
		m_vBitConnect.emplace_back();
		while (true)
		{
			const int t = m_staNodes.top();
			m_staNodes.pop();
			m_vBitConnect.back().emplace_back(t);
			if (t == next)
			{
				break;
			}
		}
		m_vBitConnect.back().emplace_back(cur);
	};
	virtual void OnBeginDFS(int cur)override {
		m_staNodes.emplace(cur);
	};
};

class Solution {
public:
    long long minimumCost(vector<int>& cost, vector<vector<int>>& roads) {
        m_c = cost.size();
        if (1 == m_c)
        {
            return cost[0];
        }
        auto neiBo = CNeiBo::Two(m_c, roads, false);
        CPointBitConnect pbc(neiBo);
        pbc.Init(neiBo);
        if (1 == pbc.m_vBitConnect.size())
        {
            return *std::min_element(cost.begin(), cost.end());
        }
        long long ans = 0;
        int iMax = 0;
        vector<bool> vCut = pbc.Cut();
        for (auto& v : pbc.m_vBitConnect)
        {
            int iCutCount = 0;
            int iCurMin = INT_MAX;
            for (const auto& iNode : v)
            {
                iCutCount += vCut[iNode];
                if (!vCut[iNode])
                {
                    iCurMin = min(iCurMin, cost[iNode]);
                }
            }
            if (1 == iCutCount)
            {
                iMax = max(iMax, iCurMin);
                ans += iCurMin;
            }
        }
        return ans - iMax;
    }
    int m_c;
};

测试用例


template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
	assert(t1 == t2);
}

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
	if (v1.size() != v2.size())
	{
		assert(false);
		return;
	}
	for (int i = 0; i < v1.size(); i++)
	{
		Assert(v1[i], v2[i]);
	}

}



int main()
{
    vector<int> cost;
    vector<vector<int>> roads;

    {
        Solution sln;
        cost = { 3,2,1,4 }, roads = { {0,2},{2,3},{3,1} };
        auto res = sln.minimumCost(cost, roads);
        Assert(2, res);
    }
    {
        Solution sln;
        cost = { 1,2,3,4,5,6 }, roads = { {0,1},{0,2},{1,3},{2,3},{1,2},{2,4},{2,5} };
        auto res = sln.minimumCost(cost, roads);
        Assert(6, res);
    }
  
}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/448290.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

5分钟搭好一个易支付,个人最简单的对接支付宝方式

最近在疯狂折腾网站相关的知识,搭建了另一个平台后,需要涉及支付相关的内容。即 用户在某个平台请求支付时候,对接第三方支付支付宝,收款信息是我的,然后支付成功后给与回调。网上很多易支付网站,但是这玩意儿,既然咱碰到了,咱就自己弄。那么说搞咱就搞。 假设你已经搭…

Kafka MQ 生产者和消费者

Kafka MQ 生产者和消费者 Kafka 的客户端就是 Kafka 系统的用户&#xff0c;它们被分为两种基本类型:生产者和消费者。除 此之外&#xff0c;还有其他高级客户端 API——用于数据集成的 Kafka Connect API 和用于流式处理 的 Kafka Streams。这些高级客户端 API 使用生产者和消…

BUUCTF---easyre1

1.记录一下第一次做逆向题目 2.题目描述&#xff0c;下载附件 3.解压之后是一个可执行文件&#xff0c;先用PE查看是否有壳 4.没有壳&#xff0c;接下来用ida打开&#xff0c;直接拖进ida即可&#xff0c;接下来使用快捷键fnshiftf12查看字符&#xff0c;若是没有出现搜索框&a…

收割机案例-简单的动态规划

#include<iostream> using namespace std; // 创建土地 short land[32][32]; short n,m;// 实际使用的土地大小 short landA[32][32];//用A收割机收割数量记录 short landB[32][32];// 用B收割机收割数量记录 int main(){cin>>n>>m;// 存储农作物产量for(sho…

GNN-Transformer新突破!全局与局部的完美融合

图神经网络&#xff08;GNN&#xff09;和Transformer的结合是近年来的研究热点。这类结合不仅能够让两者发挥各自的优势&#xff0c;还能推动模型的创新&#xff0c;提高处理图数据的效率和性能。 具体点讲&#xff0c;通过利用Transformer&#xff0c;我们可以扩展GNN的感受…

Spring boot 操作 Redis

&#x1f339;作者主页&#xff1a;青花锁 &#x1f339;简介&#xff1a;Java领域优质创作者&#x1f3c6;、Java微服务架构公号作者&#x1f604; &#x1f339;简历模板、学习资料、面试题库、技术互助 &#x1f339;文末获取联系方式 &#x1f4dd; 往期热门专栏回顾 专栏…

nginx-排查一次大文件无法正常下载问题

目录 问题现象&报错信息 问题现象以及分析 nginx报错信息 问题解决 方法1&#xff1a;配置proxy_max_temp_file_size 方法2&#xff1a;关闭proxy_buffering 参考文档 问题现象&报错信息 问题现象以及分析 文件正常从后端服务器直接下载时&#xff0c;一切正常…

【git bug】warning: auto-detection of host provider took too long (>2000ms)

【git bug】warning: auto-detection of host provider took too long (>2000ms) 报错问题&#xff1a; warning: auto-detection of host provider took too long (>2000ms) 报错截图&#xff1a; 报错描述&#xff1a; 在windows操作系统&#xff0c;未连接互连网电…

java之mybatis

准备工作 上面4步骤 XML映射文件 动态SQL

掘根宝典之c++有符号(signed)和无符号类型(unsigned)

在c中&#xff0c;有符号和无符号是针对整型而言的 在C中&#xff0c;除了布尔类型和拓展的字符类型之外&#xff0c;其他整型可以划分为有符号类型&#xff08;signed&#xff09;和无符号类型&#xff08;unsigned&#xff09;&#xff0c;用于表示整数。 有符号类型可以表…

参与Penpad launch任务,实现Penpad与Scroll的双空投

在比特币 ETF 、BTC 减半等利好消息的持续推动下&#xff0c;加密市场逐渐进入到新一轮牛市周期中。除了以太坊 Layer1 生态 TVL 不断飙升外&#xff0c;Layer2 赛道 TVL 也在不断飙升并且屡创新高。 而在牛市背景下&#xff0c;Layer2 空投所带来的财富效应预期正在被进一步拉…

AD20新建工程步骤

1 新建工程 2 创建 3 新建原理图 4 新建PCB图 5 对原理图贺PCB都进行保存 6 新建原理图库贺PCB库&#xff0c;以及保存 最后在保存位置上都可以看到 打开的时候直接打开工程&#xff0c;它自己就会把这些链接在一起

笔记本电脑使用时需要一直插电吗?笔记本正确的充电方式

随着科技的不断发展&#xff0c;笔记本电脑已经成为人们日常生活和工作中不可或缺的电子设备。而在使用笔记本电脑时&#xff0c;很多人会有一个疑问&#xff0c;那就是笔记本电脑使用时需要一直插电吗&#xff1f;本文将就此问题展开讨论。 不一定需要一直插电&#xff0c;如果…

Linux网络基础3之IP协议

(&#xff61;&#xff65;∀&#xff65;)&#xff89;&#xff9e;嗨&#xff01;你好这里是ky233的主页&#xff1a;这里是ky233的主页&#xff0c;欢迎光临~https://blog.csdn.net/ky233?typeblog 点个关注不迷路⌯▾⌯ 目前已经学完了应用层以及传输层&#xff0c;我们应…

系统学习c++类和对象——深度理解默认成员函数

前言&#xff1a;类和对象是面向对象语言的重要概念。 c身为一门既面向过程&#xff0c;又面向对象的语言。 想要学习c&#xff0c; 首先同样要先了解类和对象。 本节就类和对象的几种构造函数相关内容进行深入的讲解。 目录 类和对象的基本概念 封装 类域和类体 访问限定符…

单片机灭火避障小车设计

目录 目录 II 摘要 III 1 智能小车概述 5 1.1 国内外研究动态 5 1.2 课题的目的和意义 5 2 系统设计概述 6 2.1 系统设计要求 6 2 总体方案设计 7 2.1 硬件设计 7 2.1.1 车体设计 7 2.1.2 主控制器模块 8 2.1.3 电源模块 8 2.1.4 电机驱动模块 9 2.2 火源检测模块 10 2.3 避障…

vue实现图片框选标注

前言 前端有一个需求&#xff0c;对上传的图片进行检测识别&#xff0c;通过返回的接口坐标数据&#xff0c;对图片的某些区域进行框选并标注。如图&#xff1a; 开始 1、上传功能使用elementui的upload插件&#xff1b; 2、在图片上进行标注功能是元素定位在图片上层&#x…

小程序对于人力资源行业的创新与变革

随着移动互联网的快速发展&#xff0c;小程序成为了各行各业推广和服务的新利器。对于人力资源行业来说&#xff0c;开发一款定制化的小程序不仅可以提升服务效率&#xff0c;还可以增强品牌形象和用户粘性。那么&#xff0c;如何定制开发人力资源类的小程序呢&#xff1f;下面…

群晖Synology Office本地文件如何分享给同事远程协作编辑【内网穿透】

文章目录 本教程解决的问题是&#xff1a;1. 本地环境配置2. 制作本地分享链接3. 制作公网访问链接4. 公网ip地址访问您的分享相册5. 制作固定公网访问链接 本教程解决的问题是&#xff1a; 1.Word&#xff0c;PPT&#xff0c;Excel等重要文件存在本地环境&#xff0c;如何在编…

开源是什么?——跟老吕学Python编程

开源是什么&#xff1f;——跟老吕学Python编程 开源是什么&#xff1f;开放源代码软件是什么&#xff1f;开源软件许可证是什么&#xff1f;开放源代码软件是什么&#xff1f;开放源代码的软件代表有什么&#xff1f;开放源代码软件与自由软件的概念 开源的定义是什么&#xf…
最新文章