2018年5月4日
bzoj2561: 最小生成树（最小割）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=2561 考虑Kruscal算法求最小生成树的流程 如果 u和v之间的长为L的边能出现在最小生成树里，说明<L的边不能时u和v联通 即求图中只存在<L的边时，u和v的最小割 如果 u和v之间的长为L的边 阅读全文
posted @ 2018-05-04 17:16 TRTTG 阅读(294) 评论(0) 推荐(0)
bzoj5251: [2018多省省队联测]劈配（网络流 + 二分）
摘要： https://www.lydsy.com/JudgeOnline/problem.php?id=5251 第一问： 左边一列点代表学生，右边一列点代表导师 导师向汇点连流量为 人数限制的 边 然后从第一个学生的第一志愿往里面加边 如果当前学生的当前志愿可以满足，即目前网络流可以满流，保留这一志愿的 阅读全文
posted @ 2018-05-04 14:58 TRTTG 阅读(367) 评论(0) 推荐(0)
hihoCoder #1465 : 后缀自动机五·重复旋律8
摘要： http://hihocoder.com/problemset/problem/1465 求S的循环同构串在T中的出现次数 将串S变成SS 枚举SS的每个位置i，求出以i结尾的SS的子串 与 T的最长公共子串 若长度>=|S|，说明以i结尾的S的循环同构串在T中出现过 假设最后匹配i到达了后缀自动机 阅读全文
posted @ 2018-05-04 08:44 TRTTG 阅读(459) 评论(0) 推荐(0)