POJ 3422 Kaka's Matrix Travels(最大费用最大流 + 拆点)

题目链接:http://poj.org/problem?id=3422

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

3 2
1 2 3
0 2 1
1 4 2

Sample Output

15

Source

POJ Monthly--2007.10.06, Huang, Jinsong

题意:

在一个矩阵中,每个格子里都有一个非负数,把象棋里的车从左上角走到右下角,走 k 次,每次只能走一步,每次只能向右或向下,经过的数字即为价值(费用),并且走过某个点后,再次走这个点,那么它的费用为零,求最大和 !

PS:

一道最大费用最大流问题,

1、拆点建边:把每个点拆为两个点再在这两个点之间分别建立两条边:

第一条:他们之间的费用即为所拆点上的那个正数的相反数(这样就可以用最小费用最大流求解了,最终的答案再去一个相反数即为最大费用了),流量为 1 ;

第二条:费用为 0 ,流量为 k-1;

2、再分别向右,向下建一条费用为 0 ,流量为 k 的边!

//最大费用最小流只要在添加边的时候换一下位置就好了

//求最大费用最大流只需要把费用换成相反数,用最小费用最大流求解即可

代码如下:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
const int MAXN = 10000;
const int MAXM = 100000;
const int INF = 0x3f3f3f3f;
struct Edge
{
    int to, next, cap, flow, cost;
    int x, y;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N, M;
int map[MAXN][MAXN];
void init()
{
    N = MAXN;
    tol = 0;
    memset(head, -1, sizeof(head));
}
void addedge(int u, int v, int cap, int cost)//左端点,右端点,容量,花费
{
    edge[tol]. to = v;
    edge[tol]. cap = cap;
    edge[tol]. cost = cost;
    edge[tol]. flow = 0;
    edge[tol]. next = head[u];
    head[u] = tol++;
    edge[tol]. to = u;
    edge[tol]. cap = 0;
    edge[tol]. cost = -cost;
    edge[tol]. flow = 0;
    edge[tol]. next = head[v];
    head[v] = tol++;
}
bool spfa(int s, int t)
{
    queue<int>q;
    for(int i = 0; i < N; i++)
    {
        dis[i] = INF;
        vis[i] = false;
        pre[i] = -1;
    }
    dis[s] = 0;
    vis[s] = true;
    q.push(s);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] = false;
        for(int i = head[u]; i != -1; i = edge[i]. next)
        {
            int v = edge[i]. to;
            if(edge[i]. cap > edge[i]. flow &&
                    dis[v] > dis[u] + edge[i]. cost )
            {
                dis[v] = dis[u] + edge[i]. cost;
                pre[v] = i;
                if(!vis[v])
                {
                    vis[v] = true;
                    q.push(v);
                }
            }
        }
    }
    if(pre[t] == -1) return false;
    else return true;
}
//返回的是最大流, cost存的是最小费用
int minCostMaxflow(int s, int t, int &cost)
{
    int flow = 0;
    cost = 0;
    while(spfa(s,t))
    {
        int Min = INF;
        for(int i = pre[t]; i != -1; i = pre[edge[i^1]. to])
        {
            if(Min > edge[i]. cap - edge[i]. flow)
                Min = edge[i]. cap - edge[i]. flow;
        }
        for(int i = pre[t]; i != -1; i = pre[edge[i^1]. to])
        {
            edge[i]. flow += Min;
            edge[i^1]. flow -= Min;
            cost += edge[i]. cost * Min;
        }
        flow += Min;
    }
    return flow;
}

int main()
{
    int n, k;
    while(~scanf("%d%d",&n,&k))
    {
        init();//注意
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                int tt = (i-1)*n+j;
                addedge(tt*2,tt*2+1,1,-map[i][j]);//拆点,之间建一条负的价值的边,流量为1
                addedge(tt*2,tt*2+1,k-1,0);//再建一条价值为0,流量为k-1的边
                //printf("tt:%d tt*2:%d tt*2+1:%d ",tt,tt*2,tt*2+1);
            }
            //printf("\n");
        }
        for(int i = 1; i <= n; i++)//向右
        {
            for(int j = 1; j < n; j++)
            {
                int tt = (i-1)*n+j;//编号从2开始
                addedge(tt*2+1,(tt+1)*2,k,0);
                //printf("tt:%d tt*2:%d (tt+1)*2:%d\n",tt,tt*2,(tt+1)*2);
            }
        }
        for(int i = 1; i < n; i++)//向下
        {
            for(int j = 1; j <= n; j++)
            {
                int tt = (i-1)*n+j;
                addedge(tt*2+1,(tt+n)*2,k,0);
                //printf("tt:%d tt*2:%d (tt+n)*2:%d\n",tt,tt*2,(tt+n)*2);
            }
        }
        int beg = 1;//超级起点
        int end = 2*n*n+2;//超级汇点
        addedge(beg,2,k,0);//超级起点,容量为1,花费为0
        addedge(2*n*n+1,end,k,0);//超级汇点容量为1,花费为0
        int ans = 0;
        minCostMaxflow(beg,end,ans);
        //minCostMaxflow(2,2*n*n+1,ans);
        printf("%d\n",-ans);//相反数即为最大的价值
    }
    return 0;
}

POJ 3422 Kaka's Matrix Travels(最大费用最大流 + 拆点)

时间: 12-08

POJ 3422 Kaka's Matrix Travels(最大费用最大流 + 拆点)的相关文章

POJ 3422 Kaka&#39;s Matrix Travels(费用流)

POJ 3422 Kaka's Matrix Travels 题目链接 题意:一个矩阵,从左上角往右下角走k趟,每次走过数字就变成0,并且获得这个数字,要求走完之后,所获得数字之和最大 思路:有点类似区间k覆盖的建图方法,把点拆了,每个点有值的只能选一次,其他都是无值的,利用费用流,入点出点之间连一条容量1,有费用的边,和一条容量k - 1,费用0的边,然后其他就每个点和右边和下边2个点连边,然后跑费用流 代码: #include <cstdio> #include <cstring&g

poj 3422 Kaka&#39;s Matrix Travels (费用流)

Kaka's Matrix Travels Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7743   Accepted: 3111 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 mo

poj 3422 Kaka&#39;s Matrix Travels 最小费最大流

输入的时候没有取反,一直ole. 这里也是用到拆点,将一个点拆成p和q,这两个之间连接两条路,一条cap=1和cost=矩阵上的值,另一条为cap=k和cost=0.在将0和2*n *n+1看成源点和汇点. #include<stdio.h> #include<string.h> #include<vector> #include<queue> #include<algorithm> using namespace std; const int

POJ3422 Kaka&#39;s Matrix Travels(最大费用最大流 + 拆点)

题目链接:http://poj.org/problem?id=3422 题意:有一个n*n的矩阵,格子中的元素是费用,KaKa从左上角开始出发要到达右下角,但是他只能向下走或者向右走,且走过的格子赋值为0,可以走K次,问K次后KaKa能获得的最大费用是多少? 思路:首先解释一下为什么要拆点?    因为要获得最大费用,所以假设当前步选择先下走,最终得到的结果可能不是最大值,但根据题意却把走过的格子赋为0了,这就影响了最终结果.所以进行拆点,把每个点拆成两个点,入度点和出度点,本点的入度点连接着本

POj3422 Kaka&#39;s Matrix Travels 最小费用最大流 拆点

题目链接: poj3422 题意: 有一个N X N的矩阵, 矩阵的每一小格都有且仅有一个数字v,kaka每经过一个数字就会把它捡起来并将那个数字加到sum上去. 现在kaka能通过向下或向右走的方式从 (1,1)到(n,n)  K次,问kaka能取到的最大的sum是多少. 解题思路: 题目问题可以抽象为   求多次可走重复路的最长路的最大和问题 首先想到的就应该是最小费用最大流, 而题目要求的最大和值,那么应求就是最大费用最大流, 仅仅只需要将代码中的最小路算法改为最长路算法即可 题目的条件是

POJ 3422 Kaka&#39;s Matrix Travels 【最小费用最大流】

题意: 卡卡有一个矩阵,从左上角走到右下角,卡卡每次只能向右或者向下.矩阵里边都是不超过1000的正整数,卡卡走过的元素会变成0,问卡卡可以走k次,问卡卡最多能积累多少和. 思路: 最小费用最大流的题目. 建图自己没想出来,看了大神的建边,把每个点分解成两个点,一个代表进入一个代表出去,然后每个进入和每个出去连边,容量是1价值是这个点的矩阵的数值.然后因为可以不进去,所以起点要和别的矩阵元素的起点建边,终点也要和别的矩阵矩阵元素的起点建边,最后跑下最小费用最大流. 这题最右下角的矩阵元素需要特殊

poj 3422 Kaka&#39;s Matrix Travels 【最大费用最大流】【好题】

Kaka's Matrix Travels Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 8729   Accepted: 3498 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 mo

poj 3422 Kaka&#39;s Matrix Travels 费用流

题意: 给一个n*n的矩阵,每次从左上角走到右下角并取走其中的数,求走k次能取到的最大和. 分析: 费用流边的容量有限制的作用,费用有求和的作用,对于每个点只能取一次,容易想到把这个点拆成两个点并连上容量为1,费用为该点数的边.但明显有的流要"跳过"这个点,如何处理呢?可以加一条容量为无穷,费用为0的边,这样不参加这点费用计算的流就可以"跳过"这个点了. 代码: //poj 3422 //sep9 #include <iostream> #include

POJ 3422 Kaka&#39;s Matrix Travels (最小费用最大流)

POJ 3422 Kaka's Matrix Travels 链接:http://poj.org/problem?id=3422 题意:有一个N*N的方格,每个方格里面有一个数字.现在卡卡要从左上角走到右下角,规定每次只能向下或者向右走,每次走到一个格子,将得到该格子的数字,并且该格子的数字变为0.当卡卡走一次时,很容易求出最大值,问卡卡走k次,能够得到的最大值为多少. 思路:最小费用最大流 关键是如何构图 1. 将N*N个格点拆分为两个点(i,i + N*N),每个点之间连一条流量为1,费用为