Rewinner

图论

ACM(1) dfsdd(1) DP(6) hash(1) STL(1) 小技巧(4) 思维(6) 搜索(2) 数学(5) 数据结构(16) 未归档(70)

/ 注册

全部文章 / 图论（共24篇）

POJ 3160 Father Christmas flymouse 【Tanjar缩点 + dfs】

传送门题意：给你一个有向图，找寻一条路径使得经过的权值和最大（点可以重复经过，但是权值只加一次，点上的权值可加可不加）。思路：用tanjar缩点将图转化为DAG，在tanjar缩点过程中记录一个强连通分量中正权值和，然后再跑一边记忆化dfs即可。 ///#include<bi...

2019-02-23

0 543

Hdu 1350 Taxi Cab Scheme【最小边覆盖】

二分图：最小顶点覆盖=最大匹配最小边覆盖=顶点数-最小顶点覆盖（最大匹配）最小边覆盖：实质是个边集，这个集合里的边能覆盖所有的点，最小边覆盖是满足这个要求的所有边集中边数最少的一个。这里顶点数等于总的顶点数，是二分图两边的顶点数，不是一边。证明：设最大匹配数为m，总顶点数为n。为了使边...

2019-02-16

0 665

【HDU 1811】 Rank of Tetris 并查集+拓扑

题目链接：传送门中文题目就不阐述题意了，我最开始的想法是种类并查集，但是细想一下，发现并不可行，因为题目没有告诉有多少类型。做法：关键问题是处理等号的两个点，其实两个点相等，就相当于这两个人的排名是一样的，我们用并查集搞定这么些个相等排名的点，之后把有全序关系的点入度入图，然后拓扑排序走一发...

2018-11-05

0 378

二分图

关于最大匹配，最小点覆盖，最少路径覆盖和最大独立集的总结 (1)二分图的最大匹配匈牙利算法 (2)二分图的最小点覆盖二分图的最小点覆盖=二分图的最大匹配求最小点覆盖：从右边所有没有匹配过的点出发，按照增广路的“交替出现”的要求DFS。最终右边没有访问过的点和左边访问过的点组成最小点覆...

2018-08-06

0 603