广度优先搜索] [网格] [切点] 1263.推箱
最编程
2024-03-02 14:13:22
...
class CUnionFind
{
public:
CUnionFind(int iSize) :m_vNodeToRegion(iSize)
{
for (int i = 0; i < iSize; i++)
{
m_vNodeToRegion[i] = i;
}
m_iConnetRegionCount = iSize;
}
CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
{
for (int i = 0; i < vNeiBo.size(); i++) {
for (const auto& n : vNeiBo[i]) {
Union(i, n);
}
}
}
int GetConnectRegionIndex(int iNode)
{
int& iConnectNO = m_vNodeToRegion[iNode];
if (iNode == iConnectNO)
{
return iNode;
}
return iConnectNO = GetConnectRegionIndex(iConnectNO);
}
void Union(int iNode1, int iNode2)
{
const int iConnectNO1 = GetConnectRegionIndex(iNode1);
const int iConnectNO2 = GetConnectRegionIndex(iNode2);
if (iConnectNO1 == iConnectNO2)
{
return;
}
m_iConnetRegionCount--;
if (iConnectNO1 > iConnectNO2)
{
UnionConnect(iConnectNO1, iConnectNO2);
}
else
{
UnionConnect(iConnectNO2, iConnectNO1);
}
}
bool IsConnect(int iNode1, int iNode2)
{
return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
}
int GetConnetRegionCount()const
{
return m_iConnetRegionCount;
}
vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
{
const int iNodeSize = m_vNodeToRegion.size();
vector<int> vRet(iNodeSize);
for (int i = 0; i < iNodeSize; i++)
{
vRet[GetConnectRegionIndex(i)]++;
}
return vRet;
}
std::unordered_map<int, vector<int>> GetNodeOfRegion()
{
std::unordered_map<int, vector<int>> ret;
const int iNodeSize = m_vNodeToRegion.size();
for (int i = 0; i < iNodeSize; i++)
{
ret[GetConnectRegionIndex(i)].emplace_back(i);
}
return ret;
}
private:
void UnionConnect(int iFrom, int iTo)
{
m_vNodeToRegion[iFrom] = iTo;
}
vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
int m_iConnetRegionCount;
};
class CUnionFindMST
{
public:
CUnionFindMST(const int iNodeSize) :m_uf(iNodeSize)
{
}
void AddEdge(const int iNode1, const int iNode2, int iWeight)
{
if (m_uf.IsConnect(iNode1, iNode2))
{
return;
}
m_iMST += iWeight;
m_uf.Union(iNode1, iNode2);
}
void AddEdge(const vector<int>& v)
{
AddEdge(v[0], v[1], v[2]);
}
int MST()
{
if (m_uf.GetConnetRegionCount() > 1)
{
return -1;
}
return m_iMST;
}
private:
int m_iMST = 0;
CUnionFind m_uf;
};
class CUnionFindDirect
{
public:
CUnionFindDirect(int iSize)
{
m_vRoot.resize(iSize);
iota(m_vRoot.begin(), m_vRoot.end(), 0);
}
void Connect(bool& bConflic, bool& bCyc, int iFrom, int iTo)
{
bConflic = bCyc = false;
if (iFrom != m_vRoot[iFrom])
{
bConflic = true;
}
Fresh(iTo);
if (m_vRoot[iTo] == iFrom)
{
bCyc = true;
}
if (bConflic || bCyc)
{
return;
}
m_vRoot[iFrom] = m_vRoot[iTo];
}
int GetMaxDest(int iFrom)
{
Fresh(iFrom);
return m_vRoot[iFrom];
}
private:
int Fresh(int iNode)
{
if (m_vRoot[iNode] == iNode)
{
return iNode;
}
return m_vRoot[iNode] = Fresh(m_vRoot[iNode]);
}
vector<int> m_vRoot;
};
class CNearestMST
{
public:
CNearestMST(const int iNodeSize) :m_bDo(iNodeSize), m_vDis(iNodeSize, INT_MAX), m_vNeiTable(iNodeSize)
{
}
void Init(const vector<vector<int>>& edges)
{
for (const auto& v : edges)
{
Add(v);
}
}
void Add(const vector<int>& v)
{
m_vNeiTable[v[0]].emplace_back(v[1], v[2]);
m_vNeiTable[v[1]].emplace_back(v[0], v[2]);
}
int MST(int start)
{
int next = start;
while ((next = AddNode(next)) >= 0);
return m_iMST;
}
int MST(int iNode1, int iNode2, int iWeight)
{
m_bDo[iNode1] = true;
for (const auto& it : m_vNeiTable[iNode1])
{
if (m_bDo[it.first])
{
continue;
}
m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);
}
m_iMST = iWeight;
int next = iNode2;
while ((next = AddNode(next)) >= 0);
return m_iMST;
}
private:
int AddNode(int iCur)
{
m_bDo[iCur] = true;
for (const auto& it : m_vNeiTable[iCur])
{
if (m_bDo[it.first])
{
continue;
}
m_vDis[it.first] = min(m_vDis[it.first], (long long)it.second);
}
int iMinIndex = -1;
for (int i = 0; i < m_vDis.size(); i++)
{
if (m_bDo[i])
{
continue;
}
if ((-1 == iMinIndex) || (m_vDis[i] < m_vDis[iMinIndex]))
{
iMinIndex = i;
}
}
if (-1 != iMinIndex)
{
if (INT_MAX == m_vDis[iMinIndex])
{
m_iMST = -1;
return -1;
}
m_iMST += m_vDis[iMinIndex];
}
return iMinIndex;
}
vector<bool> m_bDo;
vector<long long> m_vDis;
vector < vector<std::pair<int, int>>> m_vNeiTable;
long long m_iMST = 0;
};
class CBFSDis
{
public:
CBFSDis(vector<vector<int>>& vNeiB, vector<int> start)
{
m_vDis.assign(vNeiB.size(), m_iNotMayDis);
queue<int> que;
for (const auto& n : start)
{
m_vDis[n] = 0;
que.emplace(n);
}
while (que.size())
{
const int cur = que.front();
que.pop();
for (const auto next : vNeiB[cur])
{
if (m_iNotMayDis != m_vDis[next])
{
continue;
}
m_vDis[next] = m_vDis[cur] + 1;
que.emplace(next);
}
}
}
public:
const int m_iNotMayDis = 1e9;
vector<int> m_vDis;
};
class C01BFSDis
{
public:
C01BFSDis(vector<vector<int>>& vNeiB0, vector<vector<int>>& vNeiB1, int s)
{
m_vDis.assign(vNeiB0.size(), -1);
std::deque<std::pair<int, int>> que;
que.emplace_back(s, 0);
while (que.size())
{
auto it = que.front();
const int cur = it.first;
const int dis = it.second;
que.pop_front();
if (-1 != m_vDis[cur])
{
continue;
}
m_vDis[cur] = it.second;
for (const auto next : vNeiB0[cur])
{
if (-1 != m_vDis[next])
{
continue;
}
que.emplace_front(next, dis);
}
for (const auto next : vNeiB1[cur])
{
if (-1 != m_vDis[next])
{
continue;
}
que.emplace_back(next, dis + 1);
}
}
}
public:
vector<int> m_vDis;
};
//堆（优先队列)优化迪杰斯特拉算法 狄克斯特拉(Dijkstra)算法详解
typedef pair<long long, int> PAIRLLI;
class CHeapDis
{
public:
CHeapDis(int n)
{
m_vDis.assign(n, -1);
}
void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
{
std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap;
minHeap.emplace(0, start);
while (minHeap.size())
{
const long long llDist = minHeap.top().first;
const int iCur = minHeap.top().second;
minHeap.pop();
if (-1 != m_vDis[iCur])
{
continue;
}
m_vDis[iCur] = llDist;
for (const auto& it : vNeiB[iCur])
{
minHeap.emplace(llDist + it.second, it.first);
}
}
}
vector<long long> m_vDis;
};
//朴素迪杰斯特拉算法
class CN2Dis
{
public:
CN2Dis(int iSize) :m_iSize(iSize), DIS(m_vDis), PRE(m_vPre)
{
}
void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
{
m_vDis.assign(m_iSize, -1);
m_vPre.assign(m_iSize, -1);
vector<bool> vDo(m_iSize);//点是否已处理
auto AddNode = [&](int iNode)
{
//const int iPreNode = m_vPre[iNode];
long long llPreDis = m_vDis[iNode];
vDo[iNode] = true;
for (const auto& it : vNeiB[iNode])
{
if (vDo[it.first])
{
continue;
}
if ((-1 == m_vDis[it.first]) || (it.second + llPreDis < m_vDis[it.first]))
{
m_vDis[it.first] = it.second + llPreDis;
m_vPre[it.first] = iNode;