题目描述
给出一个 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
说明
每个格子中的数不超过 1000
Solution:
本题费用流套路题(道道网络流题都是满满的套路啊!).
分析怎么想到费用流:
首先 $k=1$ 就是 sb 动规, 而当 $k>1$ 就要限制每个点只能选 $1$ 次, 这样限制了上下界且带权的最优性问题, 直接考虑费用流模型.
怎么建模:
1, 拆点肯定是要的, 因为有选择次数限制, 那么点 $i$ 向 $i'$ 连容量 $1$ 费用为点权的边, 又因还能选 k-1 次, 所以再从 $i$ 向 $i'$ 连容量 $k-1$ 费用 $0$ 的边.
2, 对于能转移的一对点 $i\rightarrow j$, 从 $i'$ 向 $j$ 连容量 $k$ 费用 $0$ 的边.
以 $(1,1)$ 的入点为原点,$(n,n)$ 的出点为汇点, 因为既保证了一个点权值只会贡献一次, 也保证了选了 k 条路线(最大流一定为 k), 所以满足正确性, 直接跑最大费用最大流就好了.
代码:
- /*Code by 520 -- 8.25*/
- #include<bits/stdc++.h>
- #define il inline
- #define ll long long
- #define RE register
- #define For(i,a,b) for(RE int (i)=(a);(i)<=(b);(i)++)
- #define Bor(i,a,b) for(RE int (i)=(b);(i)>=(a);(i)--)
- #define debug printf("%d %s\n",__LINE__,__FUNCTION__)
- using namespace std;
- const int N=50005,inf=-2139062144;
- int n,k,s,t,maxn[N],pre[N],dis[N],tot;
- int cnt=1,h[N],to[N],net[N],w[N],c[N];
- int maxc,maxf,mp[55][55],id[55][55];
- bool vis[N];
- il void add(int u,int v,int fl,int co){
- to[++cnt]=v,net[cnt]=h[u],w[cnt]=fl,c[cnt]=co,h[u]=cnt;
- to[++cnt]=u,net[cnt]=h[v],w[cnt]=0,c[cnt]=-co,h[v]=cnt;
- }
- il bool spfa(){
- queue<int>q;
- memset(dis,128,sizeof(dis));
- dis[s]=0,maxn[s]=1<<30,q.push(s);
- while(!q.empty()){
- RE int u=q.front();q.pop();vis[u]=0;
- for(RE int i=h[u];i;i=net[i])
- if(w[i]&&dis[to[i]]<dis[u]+c[i]){
- dis[to[i]]=dis[u]+c[i],pre[to[i]]=i,
- maxn[to[i]]=min(maxn[u],w[i]);
- if(!vis[to[i]]) vis[to[i]]=1,q.push(to[i]);
- }
- }
- return dis[t]!=inf;
- }
- il void update(){
- int x=t;
- while(x!=s){
- RE int i=pre[x];
- w[i]-=maxn[t],w[i^1]+=maxn[t];
- x=to[i^1];
- }
- maxf+=maxn[t],maxc+=maxn[t]*dis[t];
- }
- il void init(){
- scanf("%d%d",&n,&k),s=1,t=2*n*n;
- For(i,1,n) For(j,1,n) {
- id[i][j]=++tot,scanf("%d",&mp[i][j]);
- add(id[i][j],id[i][j]+n*n,1,mp[i][j]),
- add(id[i][j],id[i][j]+n*n,k-1,0);
- }
- For(i,1,n) For(j,1,n){
- if(i+1<=n) add(id[i][j]+n*n,id[i+1][j],k,0);
- if(j+1<=n) add(id[i][j]+n*n,id[i][j+1],k,0);
- }
- while(spfa()) update();
- cout<<maxc;
- }
- int main(){
- init();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2743123.html