首页 > ACM题库 > HDU-杭电 > HDU 3376-Matrix Again-高精度-[解题报告]HOJ
2014
03-16

HDU 3376-Matrix Again-高精度-[解题报告]HOJ

Matrix Again

问题描述 :

Starvae 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 starvae should to do is that choose a detour which from 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 starvae 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 starvae can not pass the same area of the Matrix except the start and end..
Do you know why call this problem as “Matrix Again”? AS it is like the problem 2686 of HDU.

输入:

The input contains multiple test cases.
Each case first line given the integer n (2<=n<=600)
Then n lines, each line include n positive integers. (<100)

输出:

The input contains multiple test cases.
Each case first line given the integer n (2<=n<=600)
Then n lines, each line include n positive integers. (<100)

样例输入:

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

样例输出:

28
46
80

#include<iostream>
#include<algorithm>
#include<cstring>
/*
题目大意是给定一个n*n的矩阵,yifenfei从起点(1, 1)这个位置一直取数到(n,n),
每取完一个数,下一个只能取当前数右方或者下方的一个数,
(注意两个数之间的距离应该是1,之前以为下方或者右方任何一个数都可以取),
就这样取到(n,n),然后再从(n,n)取回(1,1),这次每取完一个数,
下一个只能取当前数左方或者右方的一个数,最后回到(1,1),
每个数只能被取一次,求这样进行取数之后能取到的最大数
*/
#include<queue>
#include<cstdio>
using namespace std;
const int MAXN=610*610*2+2;
const int inf=1<<29;
int pre[MAXN];          // pre[v] = k:在增广路上,到达点v的边的编号为k
int dis[MAXN];          // dis[u] = d:从起点s到点u的路径长为d
int vis[MAXN];         // inq[u]:点u是否在队列中
int path[MAXN];
int head[MAXN];
int NE,tot,ans,max_flow,map[666][666];
struct node
{
    int u,v,cap,cost,next;
} Edge[MAXN<<2];
void addEdge(int u,int v,int cap,int cost)
{
    Edge[NE].u=u;
    Edge[NE].v=v;
    Edge[NE].cap=cap;
    Edge[NE].cost=cost;
    Edge[NE].next=head[u];
    head[u]=NE++;
    Edge[NE].v=u;
    Edge[NE].u=v;
    Edge[NE].cap=0;
    Edge[NE].cost=-cost;
    Edge[NE].next=head[v];
    head[v]=NE++;
}
int SPFA(int s,int t)                   //  源点为0,汇点为sink。
{
    int i;
    for(i=s;i<=t;i++) dis[i]=inf;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    dis[s] = 0;
    queue<int>q;
    q.push(s);
    vis[s] =1;
 while(!q.empty())        //  这里最好用队列,有广搜的意思,堆栈像深搜。
    {
        int u =q.front();
        q.pop();
        for(i=head[u]; i!=-1;i=Edge[i].next)
        {
            int v=Edge[i].v;
            if(Edge[i].cap >0&& dis[v]>dis[u]+Edge[i].cost)
            {
                dis[v] = dis[u] + Edge[i].cost;
                pre[v] = u;
                path[v]=i;
                if(!vis[v])
                {
                    vis[v] =1;
                    q.push(v);
                }
            }
        }
        vis[u] =0;
    }
    if(pre[t]==-1)
        return 0;
    return 1;
}
void end(int s,int t)
{
    int u, sum = inf;
    for(u=t; u!=s; u=pre[u])
    {
        sum = min(sum,Edge[path[u]].cap);
    }
    max_flow+=sum;
    for(u = t; u != s; u=pre[u])
    {
        Edge[path[u]].cap -= sum;
        Edge[path[u]^1].cap += sum;
        ans += sum*Edge[path[u]].cost;     //  cost记录的为单位流量费用,必须得乘以流量。
    }
}
int main()
{
    int i,j,n,s,t;
    while(scanf("%d",&n)!=EOF)
    {
        memset(head,-1,sizeof(head));
        NE=ans=max_flow=s=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                scanf("%d",&map[i][j]);
            }
        }
        int k=n*n;
        t=2*k+1;
         for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                addEdge(j+(i-1)*n,k+j+(i-1)*n,1,-map[i][j]);
              if(j!=n) addEdge(k+j+(i-1)*n,j+1+(i-1)*n,inf,0);///右边
              if(i!=n) addEdge(k+j+(i-1)*n,i*n+j,inf,0);///下边
            }
        }
        addEdge(s,1,2,0);
        addEdge(1,k+1,1,0);
        addEdge(2*k,t,2,0);
        addEdge(k,2*k,1,0);
        while(SPFA(s,t))
        {
            end(s,t);
        }
        printf("%d\n",-ans);
    }
    return 0;
}
/*
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

*/

参考:http://blog.csdn.net/azheng51714/article/details/8148333


  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  3. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。