ccpc2019-凯发ag旗舰厅登录网址下载

problem a chessboard

补题地址：http://acm.hdu.edu.cn/showproblem.php?pid=6532

题意：有n个点，其价值为i；分别对某一行、某一列以下的行、列有限制，求选择棋子的价值和最大

题解：费用流

       离散化坐标，每行用一个点表示，每列也用一个点表示。表示第i-1行的点向表示第i行的点连边，容量为第i行及以后能拿的棋子数的上限，费用为0，同理表示相邻列的点两两连边。若第i行第j列上有棋子，则表示第i行的点向表示第j列的点连边，容量为1，费用为该棋子的价值。可以定义源点表示第0行，汇点表示第0列，源点到汇点的最大费用流即为答案。

c 版本一

题解：最小费用最大流

dinic spfa 二分 离散化

1、离散化坐标，每行用一个点表示，每列也用一个点表示。

2、从0行(0列)递推到每一行(每一列)可以拿到的棋子，表示第i-1行的点向表示第i行的点连边，容量为第i行及以后能拿的棋子数的上限，费用为0，同理表示相邻列的点两两连边。

3、若第i行第j列上有棋子，则表示第i行的点向表示第j列的点连边，容量为1，费用为该棋子的价值。

4、可以定义源点表示第0行，汇点表示第0列，源点到汇点的最大费用流即为答案。

5、即假设有n行m列，拆分每个点，分为横坐标和纵坐标，从0行到n行，再从m列到0列。

6、