2014
03-16

# 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>
/*

（注意两个数之间的距离应该是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 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].v=u;
Edge[NE].u=v;
Edge[NE].cap=0;
Edge[NE].cost=-cost;
}
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();
{
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)
{
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++)
{
}
}
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

*/

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，比楼主的要快。