威风镰鼬

题解

/ 注册

全部文章 / 题解（共3篇）

题解 | #[HNOI2006]超级英雄HERO#

思路洛谷上额外要输出匹配方案，大家可以做一做，代码上注释了。对每个问题进行二分图最大匹配，套一个匈牙利算法的模板，如果没有找到匹配，马上跳出。代码 #include<bits/stdc++.h> using namespace std; const int maxn=2005; s...

二分图

2021-08-27

1 471

题解 | #Graph Coloring I#

思路无非就两种情况：可二涂色或者存在奇环。那么我们在dfs的过程中留意有无涂色不符的情况，没有发现就直接输出一种涂色方案就行了。现在问题就是找到奇环该怎么输出呢？因为我是个笨比所以一开始写了个tarjan记录SCC，然后去输出第一个奇数并大于1个点的SCC的每一个点编号，结果只过了45.45%（所...

搜索二分图 tarjan

2021-08-26

3 568

题解 | #[ZJOI2007]矩阵游戏#

思路本来想着这是一道最大匹配的水题，没想到忘了变量初始化WA了。用匈牙利算法水过，题意大概是这个意思，假设我们有两个点集X和Y，那么输入就可以转化为二分图两边点的连线情况。交换行列式的过程，实际上是固定一个点集，另外一个点集内部在交换位置（讲得很抽象，画图试试？）然后就可以想到只要每个点都有与之匹...

二分图图论最大匹配

2021-08-25

2 449