BZOJ分析感觉好神仙啊。对于一个长为 $a$ 、宽为 $b$ 的矩形，连一条 $(a,b)$ 的双向边。问题转换为给所有边定向，使得所有点的入度为 $1$ 且出度乘权值的和最大。考虑所有连通块，可以发现不会出现 $m>n$ 的情况。也就是说每个连通块只可能是树或基环树。如果是一棵树，画图可以得到答案为 $\displaystyle w_{root}+\sum w_i(deg_i-1)...
LuoguBZOJ分析基环树最大独立集。断掉环上任意一条边，强制某个端点不选即可。可能有多颗基环树，要累加。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cst...