Matrix (hdu 2686 最大费用最大流)

时间:2019-11-15 12:46来源:计算机教程
Matrix Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K(Java/Others) Total Submission(s): 1893 Accepted Submission(s): 1006 Problem Description Yifenfei very like play a number game in the n*nMatrix. A positive integer num

Matrix

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1893 Accepted Submission(s): 1006

Problem Description Yifenfei very like play a number game in the n*n Matrix. A positive integer number is put in each area of the Matrix.
Every time yifenfei should to do is that choose a detour which frome the top left point to the bottom right point and than back to the top left point with the maximal values of sum integers that area of Matrix yifenfei choose. But from the top to the bottom can only choose right and down, from the bottom to the top can only choose left and up. And yifenfei can not pass the same area of the Matrix except the start and end.

vnsc5858威尼斯城官网,Input The input contains multiple test cases.
Each case first line given the integer n (2<30) br=""> Than n lines,each line include n positive integers.(<100)

Output For each test case output the maximal values yifenfei can get.
Sample Input

2
10 3
5 10
3
10 3 3
2 5 3
6 7 10
5
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9

Sample Output

28
46
80

Author yifenfei
Source ZJFC 2009-3 Programming Contest
Recommend yifenfei | We have carefully selected several similar problems for you: 3376 2448 3395 3491 3313
题意:给出一个n*n的矩阵,每个点上都有一个值,现在从左上角沿着一条路径走到右下脚(只能向右或者向下),然后再从右下角回到左上角(只能向左或者向上),在这个过程中每个点只允许走一次,问路径上的权值之和最大为多少?

 

思路:这里用到费用流求解,首先添加一个超级源点s=0和超级汇点t=n*n 1,然后对每个点拆点, i 向 i` 连边,容量为1,花费为该点的权值mp[i][j],然后s与 1` 连边,容量为2,花费为0,n*n向t连边,容量为2,花费为0,最后矩阵中的点之间连边,容量为1,花费为0。最后答案为cost mp[1][1] mp[n][n]。注意数组的大小。

代码:

 

#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#pragma comment (linker,/STACK:102400000,102400000)
#define mod 1000000009
#define INF 0x3f3f3f3f
#define pi acos(-1.0)
#define eps 1e-6
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid 1,r
#define FRE(i,a,b)  for(i = a; i <= b; i  )
#define FREE(i,a,b) for(i = a; i >= b; i--)
#define FRL(i,a,b)  for(i = a; i < b; i  )
#define FRLL(i,a,b) for(i = a; i > b; i--)
#define mem(t, v)   memset ((t) , v, sizeof(t))
#define sf(n)       scanf(%d, &n)
#define sff(a,b)    scanf(%d %d, &a, &b)
#define sfff(a,b,c) scanf(%d %d %d, &a, &b, &c)
#define pf          printf
#define DBG         pf(Hi
)
typedef long long ll;
using namespace std;

const int MAXN = 2000;  //注意数组的大小
const int MAXM = 100000;

struct Edge
{
    int to,next,cap,flow,cost;
}edge[MAXM];

int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N,n,m;

void init(int n)
{
    N=n;
    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)
{
    queueq;
    for (int i=0;i 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;
}

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 mp[MAXN][MAXN];

int main()
{
#ifndef ONLINE_JUDGE
    freopen(C:/Users/asus1/Desktop/IN.txt,r,stdin);
#endif
    int i,j,t;
    while (~sf(n))
    {
        init(2*n*n 2);
        FRE(i,1,n)
            FRE(j,1,n)
                sf(mp[i][j]);
        addedge(0,1 n*n,2,0);
        addedge(n*n,2*n*n 1,2,0);
        FRE(i,1,n)
            FRE(j,1,n)
            {
                addedge((i-1)*n j,(i-1)*n j n*n,1,mp[i][j]);
                if (j 1<=n)
                    addedge((i-1)*n n*n j,(i-1)*n j 1,1,0);
                if (i 1<=n)
                    addedge((i-1)*n j n*n,i*n j,1,0);
            }
        int cost;
        int ans=minCostMaxflow(0,N-1,cost);
        printf(%d
,cost mp[1][1] mp[n][n]);
    }
    return 0;
}

 

<30)>

http://www.bkjia.com/cjjc/1027152.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1027152.htmlTechArticleMatrix (hdu 2686 最大费用最大流) Matrix Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1893 Accepted Submission(s): 10...

Matrix

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1890 Accepted Submission(s): 1005

Problem Description Yifenfei very like play a number game in the n*n Matrix. A positive integer number is put in each area of the Matrix.
Every time yifenfei should to do is that choose a detour which frome the top left point to the bottom right point and than back to the top left point with the maximal values of sum integers that area of Matrix yifenfei choose. But from the top to the bottom can only choose right and down, from the bottom to the top can only choose left and up. And yifenfei can not pass the same area of the Matrix except the start and end.

Input The input contains multiple test cases.
Each case first line given the integer n (2<30) br=""> Than n lines,each line include n positive integers.(<100)

Output For each test case output the maximal values yifenfei can get.
Sample Input

2
10 3
5 10
3
10 3 3
2 5 3
6 7 10
5
1 2 3 4 5
2 3 4 5 6
3 4 5 6 7
4 5 6 7 8
5 6 7 8 9

Sample Output

28
46
80

Author yifenfei
Source ZJFC 2009-3 Programming Contest 题意:给一个n*n的距阵,每个点都有一个值。问从(0,0)到(n-1, n-1)点(只能从左到右 或 从上到下)再回到(0,0)点(只能从右到左 或 下到上)经过的点的值总和最大是多少?每个点只能走一次。 解题:其实就是找两条从(0,0)到(n-1,n-1)总和最大的路.拆点法。每个边容量为1,费用:对于点的本身,边权为点权,非点的边权值为0。

#include
#include
#include
using namespace std;
const int MAXN = 10010;
const int MAXM = 1001000;
const int INF = 1<<30;
struct EDG{
    int to,next,cap,flow;
    int cost;  //单价
}edg[MAXM];
int head[MAXN],eid;
int pre[MAXN], cost[MAXN] ; //点0~(n-1)

void init(){
    eid=0;
    memset(head,-1,sizeof(head));
}
void addEdg(int u,int v,int cap,int cst){
    edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cost = cst;
    edg[eid].cap=cap; edg[eid].flow=0; head[u]=eid  ;

    edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cost = -cst;
    edg[eid].cap=0; edg[eid].flow=0; head[v]=eid  ;
}

bool inq[MAXN];
bool spfa(int sNode,int eNode , int n){
    queueq;
    for(int i=0; i0 && cost[v]0){
        init();
        for(int i=0; i1) maxCost =mapt[n-1][n-1];
        minCost_maxFlow(s , t , maxCost , n*n*2);
        printf("%dn",maxCost);
    }
}

<30)>

http://www.bkjia.com/cjjc/1022829.htmlwww.bkjia.comtruehttp://www.bkjia.com/cjjc/1022829.htmlTechArticleHDU 2686 Matrix(最大费用流) Matrix Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1890 Accepted Submission(s): 1005 Prob...

编辑:计算机教程 本文来源:Matrix (hdu 2686 最大费用最大流)

关键词: