Matrix Again
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 102400/102400 K (Java/Others)
Total Submission(s): 2357 Accepted Submission(s): 725
Problem Description
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.
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.
Input
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)
Each case first line given the integer n (2<=n<=600)
Then n lines, each line include n positive integers. (<100)
Output
For each test case output the maximal values starvae 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
Starvae
Source
Recommend
lcy
用网络流写了下,拆点建边,费用为该点值的负数,源点和汇点容量2,其他边容量1;
#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std; const int INF=0x3f3f3f3f; const int VM=800010; const int EM=3000010; struct Edge{ int u,v,nxt; int flow,cap; }edge[EM]; int n,cnt,head[VM],dis[VM],pre[VM]; int map[620][620],vis[VM]; void addedge(int cu,int cv,int cw,int cf){ edge[cnt].u=cu; edge[cnt].v=cv; edge[cnt].cap=cw; edge[cnt].flow=cf; edge[cnt].nxt=head[cu]; head[cu]=cnt++; edge[cnt].u=cv; edge[cnt].v=cu; edge[cnt].cap=0; edge[cnt].flow=-cf; edge[cnt].nxt=head[cv]; head[cv]=cnt++; } int src,des; int EK(){ queue<int> q; while(!q.empty()) q.pop(); int ans=0; while(1){ for(int i=0;i<=des;i++){ dis[i]=INF; vis[i]=0; } dis[src]=0; q.push(src); pre[src]=-1; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].v; if(edge[i].cap>0 && dis[v]>dis[u]+edge[i].flow){ dis[v]=dis[u]+edge[i].flow; pre[v]=i; if(!vis[v]){ vis[v]=1; q.push(v); } } } } if(dis[des]==INF) break; for(int u=des;pre[u]!=-1;u=edge[pre[u]].u){ edge[pre[u]].cap--; edge[pre[u]^1].cap++; } ans+=dis[des]; } return -ans; } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d",&n)){ cnt=0; memset(head,-1,sizeof(head)); src=0; des=2*n*n-1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&map[i][j]); addedge(src,n*n,2,0); for(int i=0;i<n;i++) for(int j=0;j<n;j++){ if(i+1<n) addedge(n*(n+i)+j,n*(i+1)+j,1,0); if(j+1<n) addedge(n*(n+i)+j,n*i+(j+1),1,0); if((i==0 && j==0) || (i==n-1 && j==n-1)) continue; addedge(i*n+j,n*(n+i)+j,1,-map[i][j]); } addedge(n*n-1,2*n*n-1,2,0); printf("%d\n",EK()+map[0][0]+map[n-1][n-1]); } return 0; }
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码