1469专题

二分图最大匹配——POJ 1469

对应POJ题目:点击打开链接 COURSES Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 17976 Accepted: 7086 Description Consider a group of N students and P courses. Each student visits zero

poj 1469 COURSES 二分图匹配初识

poj 1469 COURSES  给定一些学生和一些课程,在给定这些课程有哪些学生能上,判断出是否能选出一些学生保证每个课程都有人上 解法:二分图匹配的匈牙利算法, 先把学生和课程关系用一个矩阵存下来,然后查找学生和课程可以连接的,把连上的课程标记出是哪个学生连接上的,然后继续查找,如果满足可以连接,可是课程已经被其他学生占用了,就查找那个占用的学生是否还可以连接到其他

Codeforces 1469 F. Power Sockets —— 二分+线段树,贪心

This way 题意: 现在有一个根节点,和n条包含a[i]个节点的链。一开始所有点的颜色是白色的。你每次可以做以下操作: 找到树中某个白色节点,拿出一条链,将这个节点和链上某个节点连接,并且这两个点的颜色变成黑色,之后这条链属于树中一个部分。 你可以合并任意的链,问你离根节点第k远的白色点的深度最小是多少。 题解: 首先知道了一点:加入一条链的时候,两个白点会变成黑色,那么长度小于等