P2045 方格取数加强版
题目描述
给出一个n*n的矩阵,每一格有一个非负整数Aij,(Aij <= 1000)现在从(1,1)出发,可以往右或者往下走,最后到达(n,n),每达到一格,把该格子的数取出来,该格子的数就变成0,这样一共走K次,现在要求K次所达到的方格的数的和最大
输入输出格式
输入格式：
第一行两个数n,k（1<=n<=50, 0<=k<=10）
接下来n行,每行n个数,分别表示矩阵的每个格子的数
输出格式：
一个数,为最大和
输入输出样例
说明
每个格子中的数不超过1000
相信一定有一些人一看到N<=50就想搜索（233……），但是显然TLE。
那么对于K<=10，我记得当k<=2时,貌似用DP也能做。
这题的坑就在于“加强版”，其实这题是个图论。
再看看，不难想到这是网络流“最大流最大消费”，再看到aij<=1000，便可以将每个数取负数，就最小消费流即可。
怎么建图，是网络流中的难点。
因为每个点只能去一次，所以拆成两点，这两点之间有两条路，一条只能走一次（流量为1），但可以取到数（费用为-aij）
另一点最多能走k次，取不到数。
有人喜欢建超级源点和汇点（因为只取k次），其实不用如此。
我们从1,1点出发SPFAk次即可，注意如果有一次到不了终点直接结束！
OK，就这样AC了。注意点的位置，我用的是pos（i,j）=(i-1)*n+j，比较方便。
AC代码如下：
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define pos(i,j) (i-1)*n+j
using namespace std;
+;
*;
struct p
{
int to,w,cost,nxt;
}e[M];
],dis[N<<],pre[N<<];
];
int x,num,n,k,cnt;
void add(int u,int v,int ds,int cst)
{
e[cnt].nxt=h[u];
e[cnt].to=v;
e[cnt].w=ds;
e[cnt].cost=cst;
h[u]=cnt;
cnt++;
e[cnt].nxt=h[v];
e[cnt].to=u;
e[cnt].w=;
e[cnt].cost=-cst;
h[v]=cnt;
cnt++;
}
int solve()
{
;
while(k--)
{
memset(dis,0x3f,sizeof(dis));
memset(pre,-,sizeof(pre));
queue<int>q;
q.push();
dis[]=;
while(!q.empty())
{
int now=q.front();
q.pop();inq[now]=;
;i=e[i].nxt)
if(e[i].w&&dis[e[i].to]>dis[now]+e[i].cost)
{
dis[e[i].to]=dis[now]+e[i].cost;
pre[e[i].to]=i;
;
}
}
) return -ans;
,j=n*n+N;
)
{
mx=min(mx,e[pre[j]].w);
j=e[pre[j]^].to;
}
j=n*n+N;
)
{
ans+=e[pre[j]].cost*mx;
e[pre[j]].w-=mx;
e[pre[j]^].w+=mx;
j=e[pre[j]^].to;
}
}
return -ans;
}
int main()
{
memset(h,-,sizeof(h));
scanf("%d%d",&n,&k);
;i<=n;i++)
;j<=n;j++)
{
scanf("%d",&x);
num=pos(i,j);
add(num,num+N,,-x);add(num,num+N,k,);
,j),k,);
),k,);
}
printf("%d",solve());
;
}