二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。 在这个基础上，把每个点赋予一个非负的权值，这两个问题就转化为：二分图最小点权覆盖和二分图最大点权独立集。   二分图最小点权覆盖     从x或者y集合中选取一些点，使这些点覆盖所有的边，并且选出来的点的权值尽可能小。 建模：     原二分图中的边(u,v)替换为容量为INF的有向边(u,v)，设立源点s和汇点t

题意：中文题。。 思路：首先根据横纵坐标之和的奇偶转化成二分图，对于( i , j )来说与它冲突的只有(i - 1 , j ) ( i , j - 1 ) ( i + 1 , j ) ( i  , j + 1 )4个方格， 奇偶性相反。如果i + j是奇数那么和周围4点连边，那么问题转化求所有点权和 - 该二分图的最小点权覆盖 。我们关注最小点权覆盖 模型，建立超级起点st,超级终点e

Dylans loves tree Accepts: 49 Submissions: 262 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) 问题描述 Dylans有一棵N个点的树。每个点有点权。树上节点标号为1∼N。他得到了Q个询问，形式如下：

1003. Emergency (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue As an emergency rescue team leader of a city, you are given a special map of your c

网络流 最小点权覆盖 最大点权独立集      二分图最小点覆盖和最大独立集都可以转化为最大匹配求解。在这个基础上，把每个点赋予一个非负的权值，这两个问题就转化为：二分图最小点权覆盖和二分图最大点权独立集。       二分图最小点权覆盖     从x或者y集合中选取一些点，使这些点覆盖所有的边，并且选出来的点的权值尽可能小。 建模：     原二分图中的边(u,v)替换为容量为IN

题目连接 HDU 1565和1569同属一个问题：最大点权独立集。 这是一个二分图最大点权独立集，就是找出图中一些点，使得这些点之间没有变相连，这些点的权值之和最大。独立集与覆盖集是互补的，求最大点独立集可以转化为 最小点权覆盖集(最小点权支配集)，最小点权覆盖集问题可以转化为最小割问题。   结论： 最大点权独立集=所以点权-最小点权覆盖集=所有点权-最小割集=所有点权-网络最大流。

链接：https://ac.nowcoder.com/acm/problem/14393 来源：牛客网   题目描述 给你一棵树，最开始点权为0，每次将与一个点x树上距离<=1的所有点点权+1，之后询问这些点修改后的点权和. 输入描述: 第一行两个数n和m第二行n-1个数，第i个数fa[i + 1]表示i + 1点的父亲编号，保证fa[i + 1]<i + 1第三行m个数，每个数x依次