题目描述

给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大

输入输出格式
输入格式:

第一行两个数n,k(1<=n<=50, 0<=k<=10)

接下来n行,每行n个数,分别表示矩阵的每个格子的数

输出格式:

一个数,为最大和

输入输出样例
输入样例#1:

3 1
1 2 3
0 2 1
1 4 2

输出样例#1:

11


把一个点拆成入点和出点
对于每个点,
1.从出点到入点连一条容量为1,费用为点权的边
表示取一次
2.连一条无限流,费用0的边
表示重复走过

然后对于他可以到达的点
3.连一条无限流,费用0的边
表示移动

然后对于起始点1,1 终止点 n,n
4.从s连向1 ,1的入点 容量k费用0
限制走K次
同理
5.从n,n的出点连向t,容量k费用0

这里要求最大取值,所以把边权取负之后跑spfa就是最大流最大费用了

 

分类: 图论题解

说点什么

avatar
  Subscribe  
提醒