现在有一副若干条边的二分图,左边有n个点 ,右边有m个点 ,左边每个点有权值w[i],右边每个有权值v[i] 。一个图的子图定义为他端点的子集。一个合法的子图满足以下两个条件: 选出的点权和大于等于限制t 并且可以从图中选出若干条边,使得二分图中每个点最多被一条边覆盖,而选出的点要恰好被一条边覆盖。 求总共有多少合法的子图。
比赛的时候用meet in the middle加上搜索水了60分。其实在比赛的时候想到的离正解已经不远了,只是有一些细节没想到和因为不会证明而没有去打。 复制一波题解: 假如选出来的只有一边,那么可以直接用 hall 定理判断是否合法。但是现在选出了两 边的点,那么可以对这两边的点分别用 hall 定理判断是否合法,这是满足题目要求的必要 条件。接下来尝试证明一下这也是满足题目要求的充分条件。首先可以先把任意一组满足左 边选出子集合法的边加入。然后依次加入右边子集中的点 以及满足右边子集合法的连接 和 的边,称 是 的匹配点(加入一个点,加入一个连接它的边)。现在有三种情况: 第一种:如果 被之前加入的边覆盖,那么就丌用加边也合法。否则加入这条边,有下 面的这些情况。 第二种: 丌属于选出的子集,那么连边肯定合法。 第三种: 属于选出的子集。考虑保留当前加入的边,并删除原先覆盖 的边,设这条 边覆盖的另一个点是 。假如 丌属于选出的子集戒这是还未加入的点,肯定合法。假如 是已经加入的点,由于它匹配点肯定丌是 (因为这是 的匹配点),所以重新加入 以及覆 盖它和它匹配点的边即可。丌难发现对于 的这种情况对于每个点最多只会出现一次。 对于所有情况,都可以满足选出子集的合法性,所以选出左边的子集和右边的子集分别 满足 hall 是满足题目要求的充分条件。我们可以分别对左边和右边的点判断是否满足 hall 定理,然后就用meet in the middle统计一下方案数即可。
顺带提一波,hall定理就是若一个二分图有最大匹配,那么其充分必要条件就是左边每一个大小为k的点集必然与右边至少k个点相连。 然后判断一个子集是否满足hall定理可以用状压然后枚举其每一个子集判断是否合法,最后再判断自己是否合法即可。
新闻热点
疑难解答