Saruhiko
Saruhiko
全部文章
图论
Codeforces(1)
杂记(2)
归档
标签
去牛客网
登录
/
注册
Saruhiko
我有来路,却无归途
全部文章
/ 图论
(共4篇)
差分约束
作用 给出一些形如x-y<=b不等式的约束,询问是否满足有解。 参考博客 差分约束系统详解 Note 将约束为标题转换成图论里的最短路径问题 求未知数的最大值,那么按小于等于建图后求最短路 如果求未知数的最小值,那么按小于等于建图后求最长路即可。 代码实现 存储结构 const...
2019-11-15
0
405
km算法
作用 求二分图最大权完美匹配 参考博客 KM算法详解+模板 代码实现 存储结构 const int maxn=310; const int inf=0x3f3f3f3f; int mmp[maxn][maxn]; // 记录每个妹子和每个男生的好感度 bool book_gril[max...
2019-11-06
0
495
匈牙利算法
作用 寻找二分图最大匹配值 参考博客 趣写算法系列之–匈牙利算法 代码实现 存储结构 const int maxn=1105; bool mp[maxn][maxn];//邻接矩阵存图 bool vis[maxn]; //标记数组 int mark[maxn];//匹配的两个点 所需...
2019-11-05
0
393
二分图基础知识
二分图定义 顶点集V可分割为两个互不相交的子集,并且图中每条边依附的两个顶点都分属于这两个互不相交的子集,两个子集内的顶点不相邻。 抽象理解:将人群分为男生和女生两部分,一对一的交往 二分图匹配 在二分图的一个子图M中,M的边集中的任意两条边都不依附于同一个顶点,则称M是一个匹配。...
2019-11-04
0
505