poj 3422 Kaka's Matrix Travels (最大费用)

本文主要是介绍poj 3422 Kaka's Matrix Travels (最大费用)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：点击打开链接

Description

On an N × N chessboard with a non-negative number in each grid, Kaka starts his matrix travels with SUM = 0. For each travel, Kaka moves one rook from the left-upper grid to the right-bottom one, taking care that the rook moves only to the right or down. Kaka adds the number to SUM in each grid the rook visited, and replaces it with zero. It is not difficult to know the maximum SUM Kaka can obtain for his first travel. Now Kaka is wondering what is the maximum SUM he can obtain after his Kth travel. Note the SUM is accumulative during the K travels.

Input

The first line contains two integers N and K (1 ≤ N ≤ 50, 0 ≤ K ≤ 10) described above. The following N lines represents the matrix. You can assume the numbers in the matrix are no more than 1000.

Output

The maximum SUM Kaka can obtain after his Kth travel.

Sample Input

Sample Output

题目大意：

给出一个矩阵，求只能向下或者向右的情况下能得到的最大和。一般的是指遍历一次，而这个是可以重复走K次。每经过一次后就把该点设为0.求最大和。

ps:这个题建图的时候需要拆点。每个格子都是一个点。把一个点拆成两个，两个点之间有两条路，一个容量为1，权值为那个格子的金钱数。另一条路容量为k-1，权值为0。因为走了一次钱捡起来之后就没钱了。

这个题有下面这一张图就够了：

给出一个分析的很好的别人画的建图模型。

用堆建图，注意建图时费用取反因为求的是最大费用最后在乘-1就是要求的值了，开的数据大一点，5010回re，，

在记录最短路径时需要多看看，第一次这样用，第一次用异或求它的邻接点。。

//最大费用建边取反
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#define INF 0x3f3f3f3fusing namespace std;
///建图的
struct node
{int u,v,c,r,next;
}eage[50100];
int h[50100];
///存图 ，给一个点赋两个id，所谓的拆点
struct mode
{int id1,id2;int w;
} mp[550][550];
int S,T;
int top;int sum=0;
void add(int u,int v,int c,int r)
{eage[top].u=u;eage[top].v=v;eage[top].c=c;eage[top].r=r;eage[top].next=h[u];h[u]=top++;eage[top].u=v;eage[top].v=u;eage[top].c=0;///容量为0eage[top].r=-r;///费用相反eage[top].next=h[v];h[v]=top++;
}int dist[50100],vis[50100],pre[50100];bool spfa()
{//cout<<S<<T<<endl;return false;queue<int>q;while(!q.empty())q.pop();for(int i=0;i<=T;i++){dist[i]=INF;vis[i]=0;pre[i]=-1;}dist[0]=0;vis[0]=1;q.push(0);while(!q.empty()){int u=q.front();q.pop();vis[u]=0;for(int i=h[u];i!=-1;i=eage[i].next){//int u=eage[i].u;int v=eage[i].v;int c=eage[i].c;int r=eage[i].r;if(c&&dist[v]>dist[u]+r){dist[v]=dist[u]+r;pre[v]=i;///是记录的下标值if(!vis[v]){vis[v]=1;q.push(v);}}}}//cout<<dist[T]<<endl;// if(dist[T]!=INF)return true;if(pre[T]==-1)return false;return true;
}
void mimx()
{while(spfa()){//cout<<"@@@"<<endl;int mi=INF;for(int i=pre[T];i!=-1;i=pre[eage[i].u])///***{mi=min(mi,eage[i].c);}//cout<<mi<<"mi   d"<<endl<<endl;for(int i=pre[T];i!=-1;i=pre[eage[i].u]){eage[i].c-=mi;//int p=pre[eage[i].u];eage[i^1].c+=mi;///异或求邻接相反的点sum+=eage[i].r*mi;}}
}
int main()
{int n,k;while(~scanf("%d%d",&n,&k)){int cnt=0;S=0;T=n*n*2+1;int m=n*n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){scanf("%d",&mp[i][j].w);mp[i][j].id1=++cnt;mp[i][j].id2=mp[i][j].id1+m;}}for(int i=0;i<=2*n*n+1;i++){h[i]=-1;}//cout<<"##"<<endl;///拆点建图top=0;sum=0;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){add( mp[i][j].id1,mp[i][j].id2,1,-mp[i][j].w);add( mp[i][j].id1,mp[i][j].id2,k-1,0);}}//cout<<"**"<<endl;///向右建图for(int i=1;i<=n;i++){for(int j=1;j<n;j++){add(mp[i][j].id2,mp[i][j+1].id1,k,0);}}///向下建图for(int i=1;i<n;i++){for(int j=1;j<=n;j++){add(mp[i][j].id2,mp[i+1][j].id1,k,0);}}add(0,mp[1][1].id1,k,0);add(mp[n][n].id2,T,k,0);//cout<<"!!!"<<endl;mimx();printf("%d\n",-sum);}return 0;}

这篇关于poj 3422 Kaka's Matrix Travels (最大费用)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！