Nemo小丑鱼~

分类

题解(4)

/ 注册

全部文章（共4篇）

题解 | #插座#

链接： https://ac.nowcoder.com/acm/problem/236773 思路：首先针对每一个插座跑一遍匈牙利算法。之后针对每一个插座，扩展两个点，其与其他电器的连接方式完全复制这个插座。这样就可以模拟这个插排插在这个插座上的情况。注意：用邻接矩阵会超时。代码： #i...

2022-08-02

0 471

题解 | #中心图#

枚举每一个点针对第二个条件，缺哪些边，添哪些边就可以了针对第三个条件，用最小路径点覆盖就可以了 #include<iostream> #include<cstring> using namespace std; int n,m; const int N=1e3; int ...

2022-08-01

0 420

题解 | #画圈游戏#

将整个棋盘分为横坐标与纵坐标的和为奇数和偶数的两种，此时，棋盘就变为了一个二分图。仅针对和为奇数的点而言，若这个点为′∗′'*'′∗′，如果它能匹配到邻近的也为′∗′'*'′∗′的点，那么cnt就加二。 cnt代表被能覆盖两个星星的牌。而cnt_代表总的星星数。那么最后的结果就是cnt/2+(...

2022-08-01

0 392

题解 | #炸弹#

将每个点定义为二分图中的一条边，此时每条边都需要被他的任意一个端点覆盖，就变成了最小点覆盖问题。而最小点覆盖=最大匹配套匈牙利算法模板就好啦 #include<iostream> #include<cstring> using namespace std; const i...

C++

2022-07-31

1 416