题意给定一个DAG，你需要删掉一个点使得原图的最长路径的长度最短，求出答案和方案。\(n\le5\times10^5,m\le10^6\)分析DAG的一条路径有一个优美的性质：一定是从拓扑序小的点指向拓扑序大的点。考虑按照拓扑序从小到大处理每一个点。假设我们处理到了点\(x\)，它的拓扑序是\(i

首先考虑连边的情况。可以把\(a_i\)拆成\(\gcd(a_i,m)\times\frac{a_i}{\gcd(a_i,m)}\)，因为\(\gcd(\frac{a_i}{\gcd(a_i,m)},m)=1\)，所以与\(a_i\)有连边的\(j\)一定满足\(j\bmod\gcd(a_i,m)=0\)。于是就可以把\(c_{a_i}\)放到\(c_{\gcd(a_i,m)}\)，左部点

T1考虑二分，然后怎么check。我们随便选一个点开始BFS地移动，如果以它为左上角的正方形可以覆盖整个局面中的所有空格子，那么整个边长就是可行的。容易证明随便选一个点开始是正确的。T2抽象题。看到数据范围容易有一个状压状物，然而\(2^n\)怎么都去不掉。根据某年NOI或W

题目。关键想法：看成多项式，传点值。剩下在的等题出了再说。来了来了。可以做到\(n=94\)。提交记录。下面是做法。注：官方题解是\(n=4991\)。做法核心假设值域为\(m\)。结论：可以把\(n\)个值编码成\(2n\)个值，删\(n\)个元素后还能还原。做法：看成\(n-1\)次多项

二分图最大权匹配问题：有\(n_1\)个左部点，\(n_2\)个右部点，\(m\)条边，边有边权\(w_i\)，表示若选择这条边就会获得\(w_i\)的收益，求获得收益最大的一种图的匹配方案。若考虑用费用流求解，建立超级源点\(S\)和超级汇点\(T\)，\(S\)向每个左部点连边，流量1费用0；每个右部点向\(

给定一个\(n\)个点\(m\)条边的二分图，每个点的度数都\(\leqslantk\)，且每条边的本质不同的备选颜色数目都\(\geqslantk\)，求一组边染色，可以证明一定有解。有一个乱搞是每次在加入一条边时按照颜色从小到大，如果当前可以加入则加入，否则如果只会影响一条边则将这条边断掉后再重

二分图最大匹配和二分图最大权完美匹配二分图最大匹配题目描述对于一个二分图，求其最大匹配的边数（任意一个点只能匹配另一个点）算法解析使用匈牙利算法。遍历每一个左部点，若发现它所连到的右部点中有未被匹配的点就选择连接；若右部点已被匹配，就询问匹配该右部点的点能否更换至另