\(\mathcal{Description}\)
- 给定一张无向图，为每条边定向，定义每个点的价值为出度与入度之差的绝对值，求最大价值和。
- 对于 \(40\%\) 的数据，\(1\leq n,m\leq20\)。
- 对于 \(70\%\) 的数据，\(1\leq n\leq17\)。
- 对于 \(90\%\) 的数据，\(1\leq n\leq22\)。
- 对于所有数据，\(1\leq n\leq25\)，\(1\leq m\leq\dfrac{1}{2}n(n+1)\)。
\(\mathcal{Solution}\)
做法一
枚举每条边的方向，最后计算贡献。
时间复杂度 \(\mathcal{O}(2^m n)\)，期望得分 \(40\)。
做法二
设每个点入度 \(a_{i}\)，出度 \(b_i\)。
\[\vert x\vert=\begin{cases}x & x\geq0\\-x&x<0\end{cases} \]枚举每个点绝对值取正还是负，即为 \(a_i-b_i\) 还是 \(b_i-a_i\)。最后对每条边计算贡献：
- 设该边连接 \((u,v)\)，则等价于一点 \(a_i\) 加一，一点 \(b_i\) 加一。
- 如果 \(u,v\) 两点取的符号相同，则无法计算贡献。
- 如果 \(u,v\) 两点取的符号不同，则贡献为 \(2\)。
时间复杂度 \(\mathcal{O}(2^n(n+m))\)，期望得分 \(70\)。
做法三
状压每个点的相邻点与取值，计算即可。
时间复杂度 \(\mathcal{O}(2^n n)\)，期望得分 \(90\)。
做法四
设 \((u,v)\) 计算贡献，则只要 \(\max\{u,v\}\) 对 \(\min\{u,v\}\) 算一次贡献，答案 \(\times 2\) 即可。
那么可以一边搜一边算贡献。
时间复杂度 \(\mathcal{O}(2^n)\)，期望得分 \(100\)。
标签：得分,期望,题解,复杂度,贡献,leq,道路,mathcal,翻修 From： https://www.cnblogs.com/Milkcatqwq/p/17454342.html