【动态规划】【状态压缩】【2次选择】【广度搜索】1494. 并行课程 II

作者推荐

本文涉及知识点

状态压缩 广度优先搜索

leetcode1494. 并行课程 ii

给你一个整数 n 表示某所大学里课程的数目，编号为 1 到 n ，数组 relations 中， relations[i] = [xi, yi] 表示一个先修课的关系，也就是课程 xi 必须在课程 yi 之前上。同时你还有一个整数 k 。
在一个学期中，你 最多 可以同时上 k 门课，前提是这些课的先修课在之前的学期里已经上过了。
请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。
示例 1：
输入：n = 4, relations = [[2,1],[3,1],[1,4]], k = 2
输出：3
解释：上图展示了题目输入的图。在第一个学期中，我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ，第三个学期上课程 4 。
示例 2：
输入：n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2
输出：4
解释：上图展示了题目输入的图。一个最优方案是：第一学期上课程 2 和 3，第二学期上课程 4 ，第三学期上课程 1 ，第四学期上课程 5 。
示例 3：
输入：n = 11, relations = [], k = 2
输出：6
提示：
1 <= n <= 15
1 <= k <= n
0 <= relations.length <= n * (n-1) / 2
relations[i].length == 2
1 <= xi, yi <= n
xi != yi
所有先修关系都是不同的，也就是说 relations[i] != relations[j] 。
题目输入的图是个有向无环图。

状态压缩

15门课程。枚举最后一次选择（选择1到15门） 和之前的选择（0到15门）。共多少种可能。暴力做法是：2³⁰。

枚举第一门课 第二门课第三门课 的可能

不包括0，共7种可能。
const int imaxmask = (1 << 3)-1;
for (int mask = imaxmask; mask; mask = (mask - 1) & imaxmask)
{
char sz1[100],sz2[100];
_itoa_s(mask, sz1, 2);
_itoa_s(imaxmask - mask, sz2, 2);
std::cout << “最后一次选择:\t” << sz1 << " 之前的选择:\t" << sz2 << std::endl;
}
最后一次选择: 111 之前的选择: 0
最后一次选择: 110 之前的选择: 1
最后一次选择: 101 之前的选择: 10
最后一次选择: 100 之前的选择: 11
最后一次选择: 11 之前的选择: 100
最后一次选择: 10 之前的选择: 101
最后一次选择: 1 之前的选择: 110

枚举第一、三、四

不包括0，共7种可能，不需要枚举16种可能。自动忽略了不可能存在的状态2。
const int imaxmask = 1+4+8;

最后一次选择: 111 之前的选择: 0
最后一次选择: 110 之前的选择: 1
最后一次选择: 101 之前的选择: 10
最后一次选择: 100 之前的选择: 11
最后一次选择: 11 之前的选择: 100
最后一次选择: 10 之前的选择: 101
最后一次选择: 1 之前的选择: 110

枚举imaxmask [0,2ⁿ)

总时间复杂度是:o(3ⁿ) 3¹⁵大约1.4e7。注意剪枝，否则容易超时。

动态规划

动态规划的状态表示

pre记录i学期能够完成的课程，dp记录i+1学期可以完成的课程。vhasdo记录已经完成的状态。状态没必要重复处理，i1<i2，如果某种状态i1学期能处理，那没必要i2学期处理。
空间复杂度:状态数 ,2ⁿ
时间复杂度: o(3ⁿ)

动态规划的转移方程

当前学期的课程，必须满足三个条件：
一，课程数小于等于k。
二，所有前置课程都已经完成。
三，这些课程没学习过。可以省略，会被淘汰。
预处理：
vpre[i] 表示第i门课需要的前面状态。
vnext[mask] 记录完成mask课程后，能够学习的课程。

动态规划的初始值

pre={0}

动态规划的填表顺序

i从0到大

动态规划的返回值

pre 包括(1<<n)-1时的i。

代码

核心代码

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
	int countx = 0;
	while (x) {
		countx++;
		x &= (x - 1);
	}
	return countx;
}

class solution {
public:
	int minnumberofsemesters(int n, vector<vector<int>>& relations, int k) {
		const int imaskcount = 1 << n;
		vector<int> vpre(n);
		for (const auto& v : relations)
		{
			vpre[v[1] - 1] |= 1 << (v[0] - 1);
		}
		vector<int> vnext(imaskcount);
		for (int i = 0; i < imaskcount; i++)
		{
			for (int j = 0; j < n; j++)
			{
				if ((vpre[j] & i) == vpre[j])
				{
					vnext[i] |= (1 << j);
				}
			}
		}

		vector<int> pre = { 0 };
		vector<bool> vhasdo(imaskcount);
		for (int i = 0; ; i++)
		{
			vector<int> dp;
			for (const int& ipre : pre)
			{
				if (ipre + 1 == imaskcount)
				{
					return i;
				}
				const int iremain = (imaskcount - 1) - ipre;
				const int icansel = iremain& vnext[ipre];
				auto add = [&](const int& cur)
				{
					const int inew = cur | ipre;
					if (!vhasdo[inew])
					{
						dp.emplace_back(inew);
						vhasdo[inew] = true;
					}
				};
				if (bitcount((unsigned int)icansel) <= k)
				{
					add(icansel);
					continue;
				}
				for (int cur = icansel; cur; cur = (cur - 1) & icansel)
				{					
					if (bitcount((unsigned int)cur) == k)
					{
						add(cur);
					}
				}
			}
			pre.swap(dp);
		}
		return -1;
	}
};

测试用例

template<class t>
void assert(const t& t1, const t& 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()
{	
	int n, k;
	vector<vector<int>> relations;
	{
		solution sln;
		n = 4, relations = { {2,1},{3,1},{1,4} }, k = 2;
		auto res = sln.minnumberofsemesters(n, relations, k);
		assert(3, res);
	}
	{
		solution sln;
		n = 5, relations = { {2,1},{3,1},{4,1},{1,5} }, k = 2;
		auto res = sln.minnumberofsemesters(n, relations, k);
		assert(4, res);
	}
	{
		solution sln;
		n = 11, relations = {}, k = 2;
		auto res = sln.minnumberofsemesters(n, relations, k);
		assert(6, res);
	}
}

动态规划

剪枝 忽略非法的前者状态。

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
	int countx = 0;
	while (x) {
		countx++;
		x &= (x - 1);
	}
	return countx;
}

template<class ele,class ele2>
void minself(ele* seft, const ele2& other)
{
	*seft = min(*seft,(ele) other);
}

template<class ele>
void maxself(ele* seft, const ele& other)
{
	*seft = max(*seft, other);
}

class solution {
public:
	int minnumberofsemesters(int n, vector<vector<int>>& relations, int k) {
		const int imaskcount = 1 << n;		
		vector<int> vpre(n);
		for (const auto& v : relations)
		{
			vpre[v[1] - 1] |= 1 << (v[0] - 1);
		}
		vector<int> vnext(imaskcount), vlen(imaskcount);
		for (int i = 0; i < imaskcount; i++)
		{
			vlen[i] = bitcount((unsigned int)i);
			for (int j = 0; j < n; j++)
			{
				if ((vpre[j] & i) == vpre[j])
				{
					vnext[i] |= (1 << j);
				}
			}
		}
		vector<int> vret(imaskcount,100);
		vret[0] = 0;
		for (int i = 0; i < imaskcount; i++)
		{		
            if(vret[i] >= 100 )
            {
                continue;
            }
			const int ineedstudy = (imaskcount - 1) ^ i;//未学课程
			const int icanstudy = ineedstudy & vnext[i]; //只能学前置课程已学的课程
			if (vlen[icanstudy] <= k)
			{
				minself(&vret[i| icanstudy], vret[i] + 1);
			}
			for (int j = icanstudy; j; j= icanstudy &(j-1))
			{//i是已学课程，j是本学期将学的课程	
				if (bitcount((unsigned )j) != k )
				{
					continue;
				}
				minself(&vret[i | j], vret[i] + 1);
			}
		}	
		return vret.back();
	}
};

2023年2月第一版

class solution {
public:
int minnumberofsemesters(int n, vector<vector>& relations, int k) {
m_in = n;
m_ik = k;
m_imasknum = 1 << n;
m_vprecourse.resize(n);
for (const auto& v : relations)
{
m_vprecourse[v[1] - 1] |= (1 << (v[0] - 1));
}
m_vminsemesters.resize(m_imasknum, m_inotmay);
vector pre(1);
m_vminsemesters[0] = 0;
for (int isem = 0;; isem++)
{
vector dp;
for (const auto& pr : pre)
{
if (pr + 1 == m_imasknum)
{
return isem;
}
int icanstudy = getcanstudy(pr);
dfs(dp, pr, icanstudy, icanstudy, k,-1);
}
pre.swap(dp);
}
return 0;
}
inline int getcanstudy(int premask)const
{
int icanstudy = 0;
for (int n = 0; n < m_in; n++)
{
if (premask & (1 << n))
{//之前已经学习
continue;
}
if ((m_vprecourse[n] & premask) != m_vprecourse[n])
{//先行课程没有学习
continue;
}
icanstudy |= (1 << n);
}
return icanstudy;
}
void dfs(vector& dp, const int& premask, const int& icanstudy, int iremain, int ileve,int ipren)
{
if ((0 == ileve) || (0 == iremain))
{
const int inewmask = premask |(icanstudy - iremain );
if (m_inotmay != m_vminsemesters[inewmask])
{
return;
}
dp.push_back(inewmask);
m_vminsemesters[inewmask] = m_vminsemesters[premask] + 1;
return;
}
for (int n = ipren+1; n < m_in; n++)
{
if (iremain & (1 << n))
{
dfs(dp, premask, icanstudy, iremain -(1 << n ), ileve - 1,n);
}
}
}
vector m_vprecourse;
vector m_vminsemesters;
int m_imasknum;
int m_ik;
int m_in;
const int m_inotmay = 1000 * 1000;
};

2023年2月第二版

class solution {
public:
int minnumberofsemesters(int n, vector<vector>& relations, int k) {
m_in = n;
m_ik = k;
m_imasknum = 1 << n;
m_vprecourse.resize(n);
for (const auto& v : relations)
{
m_vprecourse[v[1] - 1] |= (1 << (v[0] - 1));
}
m_vminsemesters.resize(m_imasknum, m_inotmay);
vector pre(1);
m_vminsemesters[0] = 0;
for (int isem = 0;; isem++)
{
vector dp;
for (const auto& pr : pre)
{
if (pr + 1 == m_imasknum)
{
return isem;
}
int icanstudy = getcanstudy(pr);
dfs(dp, pr, icanstudy, icanstudy, k, icanstudy);
}
pre.swap(dp);
}
return 0;
}
inline int getcanstudy(int premask)const
{
int icanstudy = 0;
for (int n = 0; n < m_in; n++)
{
if (premask & (1 << n))
{//之前已经学习
continue;
}
if ((m_vprecourse[n] & premask) != m_vprecourse[n])
{//先行课程没有学习
continue;
}
icanstudy |= (1 << n);
}
return icanstudy;
}
void dfs(vector& dp, const int& premask, const int& icanstudy, int iremain, int ileve,int icansel)
{
if ((0 == ileve) || (0 == icansel))
{
const int inewmask = premask |(icanstudy - iremain );
if (m_inotmay != m_vminsemesters[inewmask])
{
return;
}
dp.push_back(inewmask);
m_vminsemesters[inewmask] = m_vminsemesters[premask] + 1;
return;
}
while (icansel)
{
const int inextcansel = (icansel - 1)& icansel;
const int n = icansel - inextcansel;
icansel = inextcansel;
dfs(dp, premask, icanstudy, iremain-n, ileve - 1, icansel);
}
}
vector m_vprecourse;
vector m_vminsemesters;
int m_imasknum;
int m_ik;
int m_in;
const int m_inotmay = 1000 * 1000;
};

2023年7月版

using namespace std;

template
void outtoconsoleinner(const vector& vec, const string& strsep = " ")
{
for (int i = 0; i < vec.size(); i++)
{
if (0 != i % 25)
{
std::cout << strsep.c_str();
}
std::cout << setw(3) << setfill(’ ') << vec[i];
if (0 == (i + 1) % 25)
{
std::cout << std::endl;
}
else if (0 == (i + 1) % 5)
{
std::cout << strsep.c_str();
}
}
}

class cconsole
{
public:

template<class t>
static void out(const vector<t>& vec, const string& strcolsep = " ", const string& strrowsep = "\r\n")
{
	outtoconsoleinner(vec, strcolsep);
	std::cout << strrowsep.c_str();
}

template<class t>
static void out(const vector<vector<t>>& matrix, const string& strcolsep = " ", const string& strrowsep = "\r\n")
{
	for (int i = 0; i < matrix.size(); i++)
	{
		outtoconsoleinner(matrix[i], strcolsep);
		std::cout << strrowsep.c_str();
	}
}

template<class t>
static void out(const std::map<t, std::vector<int> >& mtoppointtopoints, const string& strcolsep = " ", const string& strrowsep = "\r\n")
{
	for (auto kv : mtoppointtopoints)
	{
		std::cout << kv.first << ":";
		outtoconsoleinner(kv.second, strcolsep);
		std::cout << strrowsep.c_str();
	}
}


static void out(const  std::string& t, const string& strcolsep = " ", const string& strrowsep = "\r\n")
{
	std::cout << t.c_str() << strcolsep.c_str();
}

template<class t  >
static void out(const t& t, const string& strcolsep = " ", const string& strrowsep = "\r\n")
{
	std::cout << t << strcolsep.c_str();
}

};

void genetatesum(vector& sums, const vector& nums)
{
sums.push_back(0);
for (int i = 0; i < nums.size(); i++)
{
sums.push_back(nums[i] + sums[i]);
}
}

//[ibegin，iend]之和
long long total(int ibegin, int iend)
{
return (long long)(ibegin + iend) * (iend - ibegin + 1) / 2;
}

class cladderhlp
{
public:
cladderhlp(int ladders)
{
m_uladdernum = ladders;
}
void addneedbick(int ineedbick)
{
if (0 == m_uladdernum)
{
return;
}
if (m_ladders.size() < m_uladdernum)
{
m_ladders.push(ineedbick);
m_ieaqualbicks += ineedbick;
return;
}
int itop = m_ladders.top();
if (itop >= ineedbick)
{
return;
}
m_ieaqualbicks -= itop;
m_ieaqualbicks += ineedbick;
m_ladders.pop();
m_ladders.push(ineedbick);
}
std::priority_queue<int, vector, std::greater > m_ladders;
unsigned int m_uladdernum;
long long m_ieaqualbicks = 0;
};

struct cpeo
{
cpeo(string strname, cpeo* pparent = nullptr)
{
m_strname = strname;
m_pparent = pparent;
}
string m_strname;
vector<cpeo*> m_childs;
cpeo* m_pparent = nullptr;
};

class cneighbortable
{
public:
void init(const vector<vector>& edges)
{

}
vector<vector<int>> m_vtable;

};

//通过 x &= (x-1)实现
int bitcount(unsigned x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}

int bitcount(unsigned long long x) {
int countx = 0;
while (x) {
countx++;
x &= (x - 1);
}
return countx;
}

class crange
{
public:
template
crange(const t& v)
{
m_ibegin = 0;
m_iend = v.size();
}
bool in(int iindex)
{
return (iindex >= m_ibegin) && (iindex < m_iend);
}
const int end()
{
return m_iend;
}
protected:
int m_ibegin;
int m_iend;
};

template
class ctrie
{
public:
ctrie() :m_vpchilds(itypenum)
{

}
template<class it>
void add(it begin, it end)
{
	ctrie<itypenum, cbegin>* pnode = this;
	for (; begin != end; ++begin)
	{
		pnode = pnode->addchar(*begin).get();
	}
}
template<class it>
bool search(it begin, it end)
{
	if (begin == end)
	{
		return true;
	}

	if ('.' == *begin)
	{
		for (auto& ptr : m_vpchilds)
		{
			if (!ptr)
			{
				continue;
			}
			if (ptr->search(begin + 1, end))
			{
				return true;
			}
		}
	}

	auto ptr = getchild(*begin);
	if (nullptr == ptr)
	{
		return false;
	}
	return ptr->search(begin + 1, end);
}

protected:
std::shared_ptr addchar(char ch)
{
if ((ch < cbegin) || (ch >= cbegin + itypenum))
{
return nullptr;
}
const int index = ch - cbegin;
auto ptr = m_vpchilds[index];
if (!ptr)
{
m_vpchilds[index] = std::make_shared<ctrie<itypenum, cbegin>>();
}
return m_vpchilds[index];
}
std::shared_ptr getchild(char ch)const
{
if ((ch < cbegin) || (ch >= cbegin + itypenum))
{
return nullptr;
}
return m_vpchilds[ch - cbegin];
}
std::vector<std::shared_ptr> m_vpchilds;
};

class cwords
{
public:
void add(const string& word)
{
m_strstrs.insert(word);
}
bool search(const string& word)
{
return search(m_strstrs.begin(), m_strstrs.end(), 0, word.length(), word);
}
protected:
bool search(std::set::const_iterator begin, std::set::const_iterator end, int istrbegin, int istrend, const string& str)
{
int i = istrbegin;
for (; (i < istrend) && (str[i] != ‘.’); i++);
auto it = std::equal_range(begin, end, str, [&istrbegin, &i](const string& s, const string& sfind)
{
return s.substr(istrbegin, i - istrbegin) < sfind.substr(istrbegin, i - istrbegin);
});
if (i == istrbegin)
{
it.first = begin;
it.second = end;
}
if (it.first == it.second)
{
return false;
}
if (i == istrend)
{
return true;
}
if (i + 1 == istrend)
{
return true;
}
string tmp = str;
for (char ch = ‘a’; ch <= ‘z’; ch++)
{
tmp[i] = ch;
auto ij = std::equal_range(it.first, it.second, tmp, [&ch, &i](const string& s, const string& sfind)
{
return s[i] < sfind[i];
});
if (ij.first == ij.second)
{
continue;
}

		if (search(ij.first, ij.second, i + 1, istrend, str))
		{
			return true;
		}
	}
	return false;
}

std::set<string> m_strstrs;

};
class worddictionary {
public:
worddictionary() {
for (int i = 0; i < 26; i++)
{
m_str[i] = std::make_unique();
}
}

void addword(string word) {
	m_str[word.length()]->add(word);
}

bool search(string word) {
	return m_str[word.length()]->search(word);
}
std::unique_ptr<cwords> m_str[26];

};

template
class c1097int
{
public:
c1097int(long long lldata = 0) :m_idata(lldata% mod)
{

}
c1097int  operator+(const c1097int& o)const
{
	return c1097int(((long long)m_idata + o.m_idata) % mod);
}
c1097int& operator+=(const c1097int& o)
{
	m_idata = ((long long)m_idata + o.m_idata) % mod;
	return *this;
}
c1097int& operator-=(const c1097int& o)
{
	m_idata = (m_idata + mod - o.m_idata) % mod;
	return *this;
}
c1097int  operator-(const c1097int& o)
{
	return c1097int((m_idata + mod - o.m_idata) % mod);
}
c1097int  operator*(const c1097int& o)const
{
	return((long long)m_idata * o.m_idata) % mod;
}
c1097int& operator*=(const c1097int& o)
{
	m_idata = ((long long)m_idata * o.m_idata) % mod;
	return *this;
}
bool operator<(const c1097int& o)const
{
	return m_idata < o.m_idata;
}
c1097int pow(int n)const
{
	c1097int iret = 1, icur = *this;
	while (n)
	{
		if (n & 1)
		{
			iret *= icur;
		}
		icur *= icur;
		n >>= 1;
	}
	return iret;
}
c1097int pownegative1()const
{
	return pow(mod - 2);
}
int toint()const
{
	return m_idata;
}

private:
int m_idata = 0;;
};

template
int operator+(int idata, const c1097int& int1097)
{
int iret = int1097.operator+(c1097int(idata)).toint();
return iret;
}

template
int& operator+=(int& idata, const c1097int& int1097)
{
idata = int1097.operator+(c1097int(idata)).toint();
return idata;
}

template
int operator*(int idata, const c1097int& int1097)
{
int iret = int1097.operator*(c1097int(idata)).toint();
return iret;
}

template
int& operator*=(int& idata, const c1097int& int1097)
{
idata = int1097.operator*(c1097int(idata)).toint();
return idata;
}

template
void minself(t* seft, const t& other)
{
*seft = min(*seft, other);
}

template
void maxself(t* seft, const t& other)
{
*seft = max(*seft, other);
}

int getnotrepeatenum(int len, int ihassel)
{
if (0 == len)
{
return 1;
}
if ((0 == ihassel) && (1 == len))
{
return 10;
}
int iret = 1;
if (ihassel > 0)
{
for (int tmp = 10 - ihassel; (tmp >= 2) && len; tmp–, len–)
{
iret *= tmp;
}
}
else
{
iret *= 9;
len–;
for (int tmp = 9; (tmp >= 2) && len; len–, tmp–)
{
iret *= tmp;
}
}
return iret;
}

int gcd(int n1, int n2)
{
int t1 = min(n1, n2);
int t2 = max(n1, n2);
if (0 == t1)
{
return t2;
}
return gcd(t2 % t1, t1);
}

void createmaskvector(vector& v, const int* const p, int n)
{
const int imaxmasknum = 1 << n;
v.resize(imaxmasknum);
for (int i = 0; i < n; i++)
{
v[1 << i] = p[i];
}
for (int mask = 1; mask < imaxmasknum; mask++)
{
const int isubmask = mask & (-mask);
v[mask] = v[isubmask] + v[mask - isubmask];
}
}

class cmaxlinetree
{
public:
cmaxlinetree(int iarrsize) :m_iarrsize(iarrsize), m_vdata(iarrsize * 4)
{

}
//iindex 从0开始
void modify(int iindex, int ivalue)
{
	modify(1, 1, m_iarrsize, iindex + 1, ivalue);
}
//ineedqueryleft ineedqueryright 从0开始
int query(const int ineedqueryleft, const int ineedqueryright)
{
	return query(1, 1, m_iarrsize, ineedqueryleft + 1, ineedqueryright + 1);
}

protected:
int query(const int itreenodeindex, const int irecordleft, const int irecordright, const int ineedqueryleft, const int ineedqueryright)
{
if ((ineedqueryleft <= irecordleft) && (ineedqueryright >= irecordright))
{
return m_vdata[itreenodeindex];
}
const int imid = (irecordleft + irecordright) / 2;
int iret = 0;
if (ineedqueryleft <= imid)
{
iret = query(itreenodeindex * 2, irecordleft, imid, ineedqueryleft, ineedqueryright);
}
if (ineedqueryright > imid)
{
iret = max(iret, query(itreenodeindex * 2 + 1, imid + 1, irecordright, ineedqueryleft, ineedqueryright));
}
return iret;
}
void modify(int itreenodeindex, int ileft, int iright, int iindex, int ivalue)
{
if (ileft == iright)
{
m_vdata[itreenodeindex] = max(m_vdata[itreenodeindex], ivalue);
return;
}
const int imid = (ileft + iright) / 2;
if (iindex <= imid)
{
modify(itreenodeindex * 2, ileft, imid, iindex, ivalue);
}
else
{
modify(itreenodeindex * 2 + 1, imid + 1, iright, iindex, ivalue);
}
m_vdata[itreenodeindex] = max(m_vdata[itreenodeindex * 2], m_vdata[itreenodeindex * 2 + 1]);
}
const int m_iarrsize;
std::vector m_vdata;
};

class cmaxlinetreemap
{
public:
cmaxlinetreemap(int iarrsize) :m_iarrsize(iarrsize)
{

}
//iindex 从0开始
void modify(int iindex, int ivalue)
{
	modify(1, 1, m_iarrsize, iindex + 1, ivalue);
}
//ineedqueryleft ineedqueryright 从0开始
int query(const int ineedqueryleft, const int ineedqueryright)
{
	return query(1, 1, m_iarrsize, ineedqueryleft + 1, ineedqueryright + 1);
}

protected:
int query(const int itreenodeindex, const int irecordleft, const int irecordright, const int ineedqueryleft, const int ineedqueryright)
{
if ((ineedqueryleft <= irecordleft) && (ineedqueryright >= irecordright))
{
return m_mdata[itreenodeindex];
}
const int imid = (irecordleft + irecordright) / 2;
int iret = 0;
if (ineedqueryleft <= imid)
{
iret = query(itreenodeindex * 2, irecordleft, imid, ineedqueryleft, ineedqueryright);
}
if (ineedqueryright > imid)
{
iret = max(iret, query(itreenodeindex * 2 + 1, imid + 1, irecordright, ineedqueryleft, ineedqueryright));
}
return iret;
}
void modify(int itreenodeindex, int ileft, int iright, int iindex, int ivalue)
{
if (ileft == iright)
{
m_mdata[itreenodeindex] = max(m_mdata[itreenodeindex], ivalue);
return;
}
const int imid = (ileft + iright) / 2;
if (iindex <= imid)
{
modify(itreenodeindex * 2, ileft, imid, iindex, ivalue);
}
else
{
modify(itreenodeindex * 2 + 1, imid + 1, iright, iindex, ivalue);
}
m_mdata[itreenodeindex] = max(m_mdata[itreenodeindex * 2], m_mdata[itreenodeindex * 2 + 1]);
}
const int m_iarrsize;
std::unordered_map<int, int> m_mdata;
};

template
class csumlinetree
{
public:
csumlinetree(int ielesize) :m_ielesize(ielesize), m_varr(m_ielesize * 4), m_vchildadd(m_ielesize * 4)
{

}
void add(int ileftindex, int irightindex, int ivalue)
{
	add(1, 1, m_ielesize, ileftindex + 1, irightindex + 1, ivalue);
}
t query(int ileftindex, int irightindex)
{
	return query(1, 1, m_ielesize, ileftindex + 1, irightindex + 1);
}

private:
t query(int inode, int idataleft, int idataright, int iopeleft, int ioperight)
{
if ((iopeleft <= idataleft) && (ioperight >= idataright))
{
return m_varr[inode];
}
fresh(inode, idataleft, idataright);
const int imid = idataleft + (idataright - idataleft) / 2;
t ret(0);
if (imid >= iopeleft)
{
ret += query(inode * 2, idataleft, imid, iopeleft, ioperight);
}
if (imid + 1 <= ioperight)
{
ret += query(inode * 2 + 1, imid + 1, idataright, iopeleft, ioperight);
}
return ret;
}
/* 暴力解法
void add(int inode, int idataleft, int idataright, int iopeleft, int ioperight, int ivalue)
{
m_varr[inode] += t(ivalue)*(min(idataright, ioperight) - max(idataleft, iopeleft)+1);
if (idataleft == idataright)
{
return;
}
const int imid = idataleft + (idataright - idataleft) / 2;
if (imid >= iopeleft)
{
add(inode * 2, idataleft, imid, iopeleft, ioperight, ivalue);
}
if (imid + 1 <= ioperight)
{
add(inode * 2 + 1, imid + 1, idataright, iopeleft, ioperight, ivalue);
}
}
*/
void fresh(int inode, int idataleft, int idataright)
{
const int imid = idataleft + (idataright - idataleft) / 2;
if (m_vchildadd[inode] != 0)
{
add(inode * 2, idataleft, imid, idataleft, imid, m_vchildadd[inode]);
add(inode * 2 + 1, imid + 1, idataright, imid + 1, idataright, m_vchildadd[inode]);
m_vchildadd[inode] = 0;
}
}
//懒惰法
void add(int inode, int idataleft, int idataright, int iopeleft, int ioperight, int ivalue)
{
m_varr[inode] += t(ivalue) * (min(idataright, ioperight) - max(idataleft, iopeleft) + 1);
if ((iopeleft <= idataleft) && (ioperight >= idataright))
{
m_vchildadd[inode] += t(ivalue);
return;
}

	fresh(inode, idataleft, idataright);
	const int imid = idataleft + (idataright - idataleft) / 2;
	if (imid >= iopeleft)
	{
		add(inode * 2, idataleft, imid, iopeleft, ioperight, ivalue);
	}
	if (imid + 1 <= ioperight)
	{
		add(inode * 2 + 1, imid + 1, idataright, iopeleft, ioperight, ivalue);
	}
}

const int m_ielesize;
vector<t> m_varr;
vector<int> m_vchildadd;

};

template
class ctreearr
{
public:
ctreearr(int isize) :m_vdata(isize + 1)
{

}
void add(int index, t value)
{
	index++;
	while (index < m_vdata.size())
	{
		m_vdata[index] += value;
		index += index & (-index);
	}
}
t sum(int index)
{
	index++;
	t ret = 0;
	while (index)
	{
		ret += m_vdata[index];
		index -= index & (-index);
	}
	return ret;
}
t get(int index)
{
	return sum(index) - sum(index - 1);
}

private:
vector m_vdata;
};

//icodenum 必须大于等于可能的字符数
template
class chashstr {
public:
chashstr(string s, int icodenum, int icodebegin = 1, char chbegin = ‘a’) {
m_c = s.length();
m_vp.resize(m_c + 1);
m_vp[0] = 1;
m_vhash.resize(m_c + 1);
for (int i = 0; i < m_c; i++)
{
const int p = icodebegin + icodenum;
m_vhash[i + 1] = m_vhash[i] * p + s[i] - chbegin + icodebegin;
m_vp[i + 1] = m_vp[i] * p;
}
}
//包括left right
int gethash(int left, int right)
{
return (m_vhash[right + 1] - m_vhash[left] * m_vp[right - left + 1]).toint();
}
inline int gethash(int right)
{
return m_vhash[right + 1].toint();
}
int gethashexincluderight(int left, int right)
{
return (m_vhash[right ] - m_vhash[left] * m_vp[right - left ]).toint();
}
inline int gethashexincluderight(int right)
{
return m_vhash[right].toint();
}
int m_c;
vector<c1097int> m_vp;
vector<c1097int> m_vhash;
};

template
class c2hashstr
{
public:
c2hashstr(string s) {
m_phash1 = std::make_unique<chashstr<>>(s, 26);
m_phash2 = std::make_unique < chashstr>(s, 27, 0);
}
//包括left right
long long gethash(int left, int right)
{
return (long long)m_phash1->gethash(left, right) * (mod2 + 1) + m_phash2->gethash(left, right);
}
long long gethash(int right)
{
return (long long)m_phash1->gethash(right) * (mod2 + 1) + m_phash2->gethash(right);
}
//包括left，不包括right
long long gethashexincluderight(int left, int right)
{
return (long long)m_phash1->gethashexincluderight(left, right) * (mod2 + 1) + m_phash2->gethashexincluderight(left, right);
}
long long gethashexincluderight(int right)
{
return (long long)m_phash1->gethashexincluderight(right) * (mod2 + 1) + m_phash2->gethashexincluderight(right);
}
private:
std::unique_ptr<chashstr<>> m_phash1;
std::unique_ptr<chashstr> m_phash2;
};

template
class cdynahashstr {
public:
cdynahashstr(int icodenum, int icodebegin = 1, char chbegin = ‘a’) :m_iunit(icodenum + icodebegin), m_ip(1), m_ibegin(icodebegin - chbegin)
{

}
inline void push_back(const char& ch)
{
	const int inum = ch + m_ibegin;
	m_ihash *= m_iunit;
	m_ihash += inum;
	m_ip *= m_iunit;
}
inline void push_front(const char& ch)
{
	const int inum = ch + m_ibegin;
	m_ihash += m_ip * inum;
	m_ip *= m_iunit;
}
inline int gethash() const
{
	return m_ihash;
}
const int m_iunit;
const int m_ibegin;
c1097int<mod> m_ihash;
c1097int<mod> m_ip;

};

template
class c2dynahashstr {
public:
c2dynahashstr(int icodenum, int icodebegin = 1, char chbegin = ‘a’)
{
m_phash1 = new cdynahashstr<>(icodenum, icodebegin, chbegin);
m_phash2 = new cdynahashstr(icodenum, icodebegin, chbegin);
}
~c2dynahashstr()
{
delete m_phash1;
delete m_phash2;
}
inline void push_back(const char& ch)
{
m_phash1->push_back(ch);
m_phash2->push_back(ch);
}
inline void push_front(const char& ch)
{
m_phash1->push_front(ch);
m_phash2->push_front(ch);
}
long long hash()const
{
return (long long)mod2 * m_phash1->m_ihash.toint() + m_phash2->m_ihash.toint();
}
bool operator==(const c2dynahashstr& other) const
{
return (m_phash1->m_ihash.toint() == other.m_phash1->m_ihash.toint()) && (m_phash2->m_ihash.toint() == other.m_phash2->m_ihash.toint());
}
cdynahashstr<>* m_phash1;
cdynahashstr* m_phash2;
};
namespace nsort
{
template
bool sortvecvec(const vector& v1, const vector& v2)
{
return v1[arrindex] < v2[arrindex];
};
}

namespace ncmp
{
template
bool less(const std::pair<class1, int>& p, class1 idata)
{
return p.first < idata;
}

template<class class1>
bool  greater(const std::pair<class1, int>& p, class1 idata)
{
	return p.first > idata;
}

template<class _ty1, class _ty2>
class clesspair
{
public:
	bool operator()(const std::pair<_ty1, _ty2>& p1, const std::pair<_ty1, _ty2>& p2)const
	{
		return p1.first < p2.first;
	}
};

template<class _ty1, class _ty2>
class cgreatepair
{
public:
	bool operator()(const std::pair<_ty1, _ty2>& p1, const std::pair<_ty1, _ty2>& p2)const
	{
		return p1.first > p2.first;
	}
};

}

class cindexvector
{
public:
template
cindexvector(vector& data)
{
for (int i = 0; i < data.size(); i++)
{
m_indexs.emplace_back(i);
}
std::sort(m_indexs.begin(), m_indexs.end(), [data](const int& i1, const int& i2)
{
return data[i1] < data[i2];
});
}
int getindex(int index)
{
return m_indexs[index];
}
private:
vector m_indexs;
};

class cmedian
{
public:
void addnum(int inum)
{
m_quetopmin.emplace(inum);
makenumvalid();
makesmallbig();
}
void remove(int inum)
{
if (m_quetopmax.size() && (inum <= m_quetopmax.top()))
{
m_settopmaxdel.insert(inum);
}
else
{
m_settopmindel.insert(inum);
}

	popistopisdel(m_quetopmin, m_settopmindel);
	popistopisdel(m_quetopmax, m_settopmaxdel);
	makenumvalid();
	makesmallbig();
}
double median()
{
	const int imaxnum = m_quetopmin.size() - m_settopmindel.size();
	const int iminnum = m_quetopmax.size() - m_settopmaxdel.size();
	if (imaxnum > iminnum)
	{
		return m_quetopmin.top();
	}
	return ((double)m_quetopmin.top() + m_quetopmax.top()) / 2.0;
}
template<class t>
void popistopisdel(t& que, std::unordered_multiset<int>& settopmaxdel)
{
	while (que.size() && (settopmaxdel.count(que.top())))
	{
		settopmaxdel.erase(settopmaxdel.find(que.top()));
		que.pop();
	}
}
void makenumvalid()
{
	const int imaxnum = m_quetopmin.size() - m_settopmindel.size();
	const int iminnum = m_quetopmax.size() - m_settopmaxdel.size();
	//确保两个队的数量
	if (imaxnum > iminnum + 1)
	{
		int tmp = m_quetopmin.top();
		m_quetopmin.pop();
		m_quetopmax.emplace(tmp);
		popistopisdel(m_quetopmin, m_settopmindel);
	}
	if (iminnum > imaxnum)
	{
		int tmp = m_quetopmax.top();
		m_quetopmax.pop();
		m_quetopmin.push(tmp);
		popistopisdel(m_quetopmax, m_settopmaxdel);
	}
}
void makesmallbig()
{
	if (m_quetopmin.empty() || m_quetopmax.empty())
	{
		return;
	}
	while (m_quetopmin.top() < m_quetopmax.top())
	{
		const int ioldtopmin = m_quetopmin.top();
		const int ioldtopmax = m_quetopmax.top();
		m_quetopmin.pop();
		m_quetopmax.pop();
		m_quetopmin.emplace(ioldtopmax);
		m_quetopmax.emplace(ioldtopmin);
		popistopisdel(m_quetopmin, m_settopmindel);
		popistopisdel(m_quetopmax, m_settopmaxdel);
	}
}
std::priority_queue<int> m_quetopmax;
std::priority_queue<int, vector<int>, greater<int>> m_quetopmin;
std::unordered_multiset<int> m_settopmaxdel, m_settopmindel;

};

template
class cdistancegrid
{
public:
cdistancegrid(const vector<vector>& grid) :m_grid(grid), m_r(grid.size()), m_c(grid[0].size())
{

}
//单源路径 d 算法 ,时间复杂度:r*c*log(r*c)
inline int dis(int r1, int c1, int r2, int c2)
{
	vector<vector<int>> vdis(imaxrow, vector<int>(imaxcol, int_max));

	auto add = [&vdis, this](std::priority_queue<pair<int, int>, vector<std::pair<int, int>>, greater<pair<int, int>>>& quecur, int idis, int r, int c)
	{
		const int irowcolmask = imaxcol * r + c;
		if (idis >= vdis[r][c])
		{
			return;
		}
		quecur.emplace(idis, irowcolmask);
		vdis[r][c] = idis;
	};
	auto move = [&](std::priority_queue<pair<int, int>, vector<std::pair<int, int>>, greater<pair<int, int>>>& quecur, int idis, int r, int c)
	{
		if ((r < 0) || (r >= m_r))
		{
			return;
		}
		if ((c < 0) || (c >= m_c))
		{
			return;
		}
		if (m_grid[r][c] < 1)
		{
			return;
		}
		add(quecur, idis, r, c);
	};

	std::priority_queue<pair<int, int>, vector<std::pair<int, int>>, greater<pair<int, int>>> que;
	add(que, 0, r1, c1);
	while (que.size())
	{
		const int idis = que.top().first;
		const int istart = que.top().second;
		que.pop();
		const int r = istart / imaxcol;
		const int c = istart % imaxcol;
		if ((r == r2) && (c == c2))
		{
			return idis;
		}
		if (idis > vdis[r][c])
		{
			continue;
		}

		move(que, idis + 1, r + 1, c);
		move(que, idis + 1, r - 1, c);
		move(que, idis + 1, r, c + 1);
		move(que, idis + 1, r, c - 1);
	}

	return -1;
}

private:
virtual bool iscanmovestatue(int r, int c)
{
return m_grid[r][c] >= 1;
}
const int m_r;
const int m_c;
const vector<vector>& m_grid;

};

class cbfsgriddist
{
public:
cbfsgriddist(const vector<vector>& bcanvisit, int r, int c) :m_bcanvisit(bcanvisit), m_r(m_bcanvisit.size()), m_c(m_bcanvisit[0].size())
{
m_vdis.assign(m_r, vector(m_c, int_max / 2));
dist(r, c);
}
bool vilid(const int r, const int c)
{
if ((r < 0) || (r >= m_r))
{
return false;
}
if ((c < 0) || (c >= m_c))
{
return false;
}
return true;
}
const vector<vector>& dis()const
{
return m_vdis;
}
const vector<vector>& m_bcanvisit;
private:
//int_max/2 表示无法到达
void dist(int r, int c)
{
m_vdis.assign(m_r, vector(m_c, int_max / 2));
vector<vector> vhasdo(m_r, vector(m_c));
std::queue<std::pair<int, int>> que;
auto add = [&](const int& r, const int& c, const int& idis)
{
if (!vilid(r, c))
{
return;
}
if (vhasdo[r][c])
{
return;
}
if (!m_bcanvisit[r][c])
{
vhasdo[r][c] = true;
return;
}
if (idis >= m_vdis[r][c])
{
return;
}

		que.emplace(r, c);
		m_vdis[r][c] = idis;
		vhasdo[r][c] = true;
	};
	add(r, c, 0);
	while (que.size())
	{
		const int r = que.front().first;
		const int c = que.front().second;
		que.pop();
		const int idis = m_vdis[r][c];
		add(r + 1, c, idis + 1);
		add(r - 1, c, idis + 1);
		add(r, c + 1, idis + 1);
		add(r, c - 1, idis + 1);
	}

}
vector<vector<int>> m_vdis;
const int m_r;
const int m_c;

};

class c2bnumtrienode
{
public:
c2bnumtrienode()
{
m_childs[0] = m_childs[1] = nullptr;
}
bool getnot0child(bool bfirstright)
{
auto ptr = m_childs[bfirstright];
if (ptr && (ptr->m_inum > 0))
{
return bfirstright;
}
return !bfirstright;
}
int m_inum = 0;
c2bnumtrienode* m_childs[2];
};

template
class c2bnumtrie
{
public:
c2bnumtrie()
{
m_proot = new c2bnumtrienode();
}
void add(int inum)
{
m_sethas.emplace(inum);
c2bnumtrienode* p = m_proot;
for (int i = ilevenum - 1; i >= 0; i–)
{
p->m_inum++;
bool bright = inum & (1 << i);
if (nullptr == p->m_childs[bright])
{
p->m_childs[bright] = new c2bnumtrienode();
}
p = p->m_childs[bright];
}
p->m_inum++;
}
void del(int inum)
{
auto it = m_sethas.find(inum);
if (m_sethas.end() == it)
{
return;
}
m_sethas.erase(it);
c2bnumtrienode* p = m_proot;
for (int i = ilevenum - 1; i >= 0; i–)
{
p->m_inum–;
bool bright = inum & (1 << i);
p = p->m_childs[bright];
}
p->m_inum–;
}
int maxxor(int inum)
{
c2bnumtrienode* p = m_proot;
int iret = 0;
for (int i = ilevenum - 1; i >= 0; i–)
{
bool bright = !(inum & (1 << i));
bool bsel = p->getnot0child(bright);
p = p->m_childs[bsel];
if (bsel == bright)
{
iret |= (1 << i);
}
}
return iret;
}
c2bnumtrienode* m_proot;
std::unordered_multiset m_sethas;
};

struct svalueitem
{
svalueitem()
{

}
svalueitem(int ivalue)
{
	m_icoefficient = ivalue;
}
svalueitem operator*(const svalueitem& o)const
{
	svalueitem ret(m_icoefficient * o.m_icoefficient);
	int i = 0, j = 0;
	while ((i < m_vvars.size()) && (j < o.m_vvars.size()))
	{
		if (m_vvars[i] < o.m_vvars[j])
		{
			ret.m_vvars.emplace_back(m_vvars[i]);
			i++;
		}
		else
		{
			ret.m_vvars.emplace_back(o.m_vvars[j]);
			j++;
		}
	}
	ret.m_vvars.insert(ret.m_vvars.end(), m_vvars.begin() + i, m_vvars.end());
	ret.m_vvars.insert(ret.m_vvars.end(), o.m_vvars.begin() + j, o.m_vvars.end());
	return ret;
}
bool operator<(const svalueitem& o)const
{
	if (m_vvars.size() == o.m_vvars.size())
	{
		return m_vvars < o.m_vvars;
	}
	return m_vvars.size() > o.m_vvars.size();
}
vector<std::string> m_vvars;
int m_icoefficient = 1;//系数、倍率
std::string tostring()const
{
	std::ostringstream os;
	os << m_icoefficient;
	for (const auto& s : m_vvars)
	{
		os << "*" << s;
	}
	return os.str();
}

};

struct svalue
{
svalue()
{

}
svalue(int ivalue)
{
	svalueitem item;
	item.m_icoefficient = ivalue;
	m_items.emplace(item);
}
svalue(std::string strname)
{
	svalueitem item;
	item.m_vvars.emplace_back(strname);
	m_items.emplace(item);
}
svalue operator-(const svalue& o)const
{
	svalue ret;
	ret.m_items = m_items;
	for (auto it : o.m_items)
	{
		ret -= it;
	}
	return ret;
}
svalue operator+(const svalue& o)const
{
	svalue ret;
	ret.m_items = m_items;
	for (auto it : o.m_items)
	{
		ret += it;
	}
	return ret;
}
svalue operator*(const svalue& o)const
{
	svalue ret;
	for (const auto it : m_items)
	{
		for (const auto ij : o.m_items)
		{
			ret += it * ij;
		}
	}
	return ret;
}
svalue& operator+=(const svalueitem& item)
{
	auto it = m_items.find(item);
	if (m_items.end() == it)
	{
		m_items.emplace(item);
	}
	else
	{
		auto tmp = *it;
		tmp.m_icoefficient += item.m_icoefficient;
		m_items.erase(it);
		m_items.emplace(tmp);
	}
	return *this;
}
svalue& operator-=(const svalueitem& item)
{
	auto it = m_items.find(item);
	if (m_items.end() == it)
	{
		auto tmp = item;
		tmp.m_icoefficient *= -1;
		m_items.emplace(tmp);
	}
	else
	{
		auto tmp = *it;
		tmp.m_icoefficient -= item.m_icoefficient;
		m_items.erase(it);
		m_items.emplace(tmp);
	}
	return *this;
}
vector<std::string> tostrings()const
{
	vector<std::string> vret;
	for (const auto& item : m_items)
	{
		if (0 == item.m_icoefficient)
		{
			continue;
		}
		vret.emplace_back(item.tostring());
	}
	return vret;
}
std::set<svalueitem> m_items;

};

class cdelindexs
{
public:
cdelindexs()
{

}
cdelindexs(int isize)
{
	init(isize);
}
void init(int isize)
{
	m_bdels.assign(isize, false);
	m_vnext.resize(isize);
	for (int i = 0; i < isize; i++)
	{
		m_vnext[i] = i + 1;
	}
}
void del(int index)
{
	if ((index < 0) || (index >= m_vnext.size()))
	{
		return;
	}
	if (m_bdels[index])
	{
		return;
	}
	m_bdels[index] = true;

}
void setcur(int index)
{
	if (index < 0)
	{
		m_icur = m_vnext.size();
	}
	else
	{
		m_icur = freshcur(index);
	}
}
int nextindex()
{
	if (m_icur >= m_vnext.size())
	{
		return -1;
	}
	auto ret = m_icur;
	setcur(m_vnext[m_icur]);
	return ret;
}

private:
int freshcur(int index)
{
if (index >= m_vnext.size())
{
return m_vnext.size();
}
if (!m_bdels[index])
{
return index;
}

	return m_vnext[index] = freshcur(m_vnext[index]);
}
int m_icur = 0;
vector<bool> m_bdels;
vector<int> m_vnext;

};

class cunionfind
{
public:
cunionfind(int isize) :m_vnodetoregion(isize)
{
for (int i = 0; i < isize; i++)
{
m_vnodetoregion[i] = i;
}
m_iconnetregioncount = isize;
}
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;
}

private:
void unionconnect(int ifrom, int ito)
{
m_vnodetoregion[ifrom] = ito;
}
vector 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 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;

};

typedef pair<long long, int> pairlli;
class cdis
{
public:
static void dis(vector& vdis, int start, const vector<vector<pair<int, int>>>& vneib)
{
std::priority_queue<pairlli, vector, greater> 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 != vdis[icur])
{
continue;
}
vdis[icur] = lldist;
for (const auto& it : vneib[icur])
{
minheap.emplace(lldist + it.second, it.first);
}
}

}

};

class cnearestdis
{
public:
cnearestdis(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;
			}
		}

		long long llmindis = llong_max;
		int iminindex = -1;
		for (int i = 0; i < m_vdis.size(); i++)
		{
			if (vdo[i])
			{
				continue;
			}
			if (-1 == m_vdis[i])
			{
				continue;
			}
			if (m_vdis[i] < llmindis)
			{
				iminindex = i;
				llmindis = m_vdis[i];
			}
		}
		return (llong_max == llmindis) ? -1 : iminindex;
	};

	int next = start;
	m_vdis[start] = 0;
	while (-1 != (next = addnode(next)));
}
void cal(const int start, vector<vector<int>>& edges)
{
	vector<vector<pair<int, int>>> vneib(m_isize);
	for (int i = 0; i < edges.size(); i++)
	{
		const auto& v = edges[i];
		vneib[v[0]].emplace_back(v[1], v[2]);
		vneib[v[1]].emplace_back(v[0], v[2]);
	}
	cal(start, vneib);
}
const vector<long long>& dis;
const vector<int>& pre;

private:
const int m_isize;
vector m_vdis;//各点到起点的最短距离
vector m_vpre;//最短路径的前一点
};

class cneibo2
{
public:
cneibo2(int n, vector<vector>& edges, bool bdirect)
{
m_vneib.resize(n);
for (const auto& v : edges)
{
m_vneib[v[0]].emplace_back(v[1]);
if (!bdirect)
{
m_vneib[v[1]].emplace_back(v[0]);
}
}
}
vector<vector> m_vneib;
};

struct sdecimal
{
sdecimal(int inum = 0, int ideno = 1)
{
m_inum = inum;
m_ideno = ideno;
int igcd = gcd(abs(m_inum), abs(m_ideno));
m_inum /= igcd;
m_ideno /= igcd;
if (m_ideno < 0)
{
m_ideno = -m_ideno;
m_inum = -m_inum;
}
}
sdecimal operator*(const sdecimal& o)const
{
return sdecimal(m_inum * o.m_inum, m_ideno * o.m_ideno);
}
sdecimal operator/(const sdecimal& o)const
{
return sdecimal(m_inum * o.m_ideno, m_ideno * o.m_inum);
}
sdecimal operator+(const sdecimal& o)const
{
const int igcd = gcd(m_ideno, o.m_ideno);
const int ideno = m_ideno * o.m_ideno / igcd;
return sdecimal(m_inum * (ideno / m_ideno) + o.m_inum * (ideno / o.m_ideno), ideno);
}
sdecimal operator-(const sdecimal& o)const
{
const int igcd = gcd(m_ideno, o.m_ideno);
const int ideno = m_ideno * o.m_ideno / igcd;
return sdecimal(m_inum * (ideno / m_ideno) - o.m_inum * (ideno / o.m_ideno), ideno);
}
bool operator==(const sdecimal& o)const
{
return (m_inum == o.m_inum) && (m_ideno == o.m_ideno);
}
bool operator<(const sdecimal& o)const
{
auto tmp = *this - o;
return tmp.m_inum < 0;
}
int m_inum = 0;//分子
int m_ideno = 1;//分母
};

struct point {
double x, y;
point(double i, double j) :x(i), y(j) {}
};

//算两点距离
double dist(double x1, double y1, double x2, double y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

//计算圆心
point circlecenter(point& a, point& b, int r) {
//算中点
point mid((a.x + b.x) / 2.0, (a.y + b.y) / 2.0);
//ab距离的一半
double d = dist(a.x, a.y, mid.x, mid.y);
//计算h
double h = sqrt(r * r - d * d);
//计算垂线
point ba(b.x - a.x, b.y - a.y);
point hd(-ba.y, ba.x);
double len = sqrt(hd.x * hd.x + hd.y * hd.y);
hd.x /= len, hd.y /= len;
hd.x *= h, hd.y *= h;
return point(hd.x + mid.x, hd.y + mid.y);
}

class c01linetree
{
public:
c01linetree(const vector& nums) :m_ielesize(nums.size())
{
m_arr.resize(m_ielesize * 4);
init(nums, 1, 1, m_ielesize);
m_vneedfreshchilds.assign(m_ielesize * 4, false);
}
void rotato(int ileftzeroindex, int irightzeroindex)
{
int irotatoleft = ileftzeroindex + 1;
int irotatoright = irightzeroindex + 1;
rotato(1, 1, m_ielesize, irotatoleft, irotatoright);
}
int query()
{
return m_arr[1];
}
private:
void rotato(int isaveindex, int idatabegin, int idataend, int irotatoleft, int irotatoright)
{
if ((irotatoleft <= idatabegin) && (irotatoright >= idataend))
{//整个范围需要更新
rotatoself(isaveindex, idatabegin, idataend);
return;
}
int imid = idatabegin + (idataend - idatabegin) / 2;
if (m_vneedfreshchilds[isaveindex])
{
rotatoself(isaveindex * 2, idatabegin, imid);
rotatoself(isaveindex * 2 + 1, imid + 1, idataend);
m_vneedfreshchilds[isaveindex] = false;
}
if (imid >= irotatoleft)
{
rotato(isaveindex * 2, idatabegin, imid, irotatoleft, irotatoright);
}
if (imid + 1 <= irotatoright)
{
rotato(isaveindex * 2 + 1, imid + 1, idataend, irotatoleft, irotatoright);
}
m_arr[isaveindex] = m_arr[isaveindex * 2] + m_arr[isaveindex * 2 + 1];
}
void rotatoself(int isaveindex, int idatabegin, int idataend)
{
//总数量 - 翻转后0(翻转前1）的数量
m_arr[isaveindex] = (idataend - idatabegin + 1) - m_arr[isaveindex];
//懒惰法，标记本节点的子孙节点没更新
m_vneedfreshchilds[isaveindex] = !m_vneedfreshchilds[isaveindex];
}
void init(const vector& nums, int isaveindex, int idatabegin, int idataend)
{
if (idatabegin == idataend)
{
m_arr[isaveindex] = nums[idatabegin - 1];
return;
}
int imid = idatabegin + (idataend - idatabegin) / 2;
init(nums, isaveindex * 2, idatabegin, imid);
init(nums, isaveindex * 2 + 1, imid + 1, idataend);
m_arr[isaveindex] = m_arr[isaveindex * 2] + m_arr[isaveindex * 2 + 1];
}
const int m_ielesize;
vector m_arr;
vector m_vneedfreshchilds;
};

/*
struct treenode {
int val;
treenode *left;
treenode *right;
treenode(int x) : val(x), left(null), right(null) {}
treenode(int x, int ileft) : val(x), left(new treenode(ileft)), right(nullptr) {}
treenode(int x, int ileft, int irghit) : val(x), left(new treenode(ileft)), right(new treenode(irghit)) {}
};

namespace ntree
{
treenode* init(const vector& nums, int inull = 10000)
{
if (0 == nums.size())
{
return nullptr;
}
vector<treenode*> ptrs(nums.size() + 1), ptrparent(1);
for (int i = 0; i < nums.size(); i++)
{
if (inull == nums[i])
{
continue;
}
const int ino = i + 1;
ptrs[ino] = new treenode(nums[i]);
ptrparent.emplace_back(ptrs[ino]);
if (1 == ino)
{
continue;
}
if (ino & 1)
{//奇数是右支
ptrparent[ino / 2]->right = ptrs[ino];
}
else
{
ptrparent[ino / 2]->left = ptrs[ino];
}
}
return ptrs[1];
}
}
*/

class solution {
public:
int minnumberofsemesters(int n, vector<vector>& relations, int k) {
m_imasknum = 1 << n;
vector dp(m_imasknum,1000*1000),vpre(m_imasknum);
for (const auto& v : relations)
{
vpre[1 << (v[1] - 1)] |= (1 << (v[0] - 1));
}
dp[0] = 0;
for (int i = 0; i < m_imasknum; i++)
{
vpre[i] = vpre[i & (-i)] | vpre[i & (i - 1)];
if ((i | vpre[i]) != i)
{
continue;//非发课程：前置课程没学
}
unsigned int ucanstudy = vpre[i] ^ i;
if (bitcount(ucanstudy) <= k)
{
dp[i ] = min(dp[i ], dp[i- ucanstudy] + 1);
continue;
}
for (unsigned int ustudy = ucanstudy; ustudy; ustudy = ucanstudy & (ustudy - 1))
{
if (bitcount(ustudy) <= k)
{
dp[i] = min(dp[i ], dp[i - ustudy] + 1);
}
}
}
return dp.back();
}
int m_imasknum;
};
.

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步csdn学院，听白银讲师（也就是鄙人）的讲解。

如何你想快

速形成战斗了，为老板分忧，请学习c#入职培训、c++入职培训等课程

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版

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

测试环境

操作系统：win7 开发环境： vs2019 c++17
或者 操作系统：win10 开发环境： vs2022 c++17
如无特殊说明，本算法用**c++**实现。