三取方格数
时间限制: 1 Sec 内存限制: 128 MB题目描述
设有N*N的方格图，我们将其中的某些方格填入正整数，
而其他的方格中放入0。
某人从图得左上角出发，可以向下走，也可以向右走，直到到达右下角。
在走过的路上，他取走了方格中的数。（取走后方格中数字变为0）
此人从左上角到右下角共走3次，试找出3条路径，使得取得的数总和最大。
输入
第一行:N (4<=N<=20)
接下来一个N*N的矩阵，矩阵中每个元素不超过80，不小于0
输出
一行，表示最大的总和。
样例输入
样例输出
(x1-1,y1)->(x1,y1)向右 (x2,x1-1+y1-x2)->(x2,x1+y1-x2)向下 (x3,x1-1+y1-x3)->(x3,x1+y1-x3)向下
(x1-1,y1)->(x1,y1)向右 (x2,x1-1+y1-x2)->(x2,x1+y1-x2)向下 (x3-1,x1+y1-x3)->(x3,x1+y1-x3)向右
(x1-1,y1)->(x1,y1)向右 (x2-1,x1+y1-x2)->(x2,x1+y1-x2)向右 (x3,x1-1+y1-x3)->(x3,x1+y1-x3)向下
(x1-1,y1)->(x1,y1)向右 (x2-1,x1+y1-x2)->(x2,x1+y1-x2)向右 (x3-1,x1+y1-x3)->(x3,x1+y1-x3)向右
(x1,y1-1)->(x1,y1)向下 (x2,x1+y1-1-x2)->(x2,x1+y1-x2)向下，(x3,x1+y1-1-x3)->(x3,x1+y1-x3)向下
(x1,y1-1)->(x1,y1)向下 (x2,x1+y1-1-x2)->(x2,x1+y1-x2)向下，(x3-1,x1+y1-x3)->(x3,x1+y1-x3)向右
(x1,y1-1)->(x1,y1)向下 (x2-1,x1+y1-x2)->(x2,x1+y1-x2)向右，(x3,x1+y1-1-x3)->(x3,x1+y1-x3)向下
(x1,y1-1)->(x1,y1)向下 (x2-1,x1+y1-x2)->(x2,x1+y1-x2)向右，(x3-1,x1+y1-x3)->(x3,x1+y1-x3)向右
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=21; int gi() { int str=0; char ch=getchar(); while(ch>'9' || ch<'0')ch=getchar(); while(ch>='0' && ch<='9')str=str10+ch-48,ch=getchar(); return str; } int f[N*2][N][N][N],a[N][N]; int main() { int n=gi(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) a[i][j]=gi(); int tmp=0,from,to; for(int i=1; i<n+n; i++) { from=i-n+1>1?i-n+1:1; to=i<n?i:n; for(int j=from; j<=to; j++) { for(int k=from; k<=to; k++) { for(int g=from; g<=to; g++) { tmp=0; if(f[i-1][j][k][g]>tmp)tmp=f[i-1][j][k][g]; if(f[i-1][j-1][k][g]>tmp)tmp=f[i-1][j-1][k][g]; if(f[i-1][j][k-1][g]>tmp)tmp=f[i-1][j][k-1][g]; if(f[i-1][j][k][g-1]>tmp)tmp=f[i-1][j][k][g-1]; if(f[i-1][j-1][k-1][g]>tmp)tmp=f[i-1][j-1][k-1][g]; if(f[i-1][j-1][k][g-1]>tmp)tmp=f[i-1][j-1][k][g-1]; if(f[i-1][j][k-1][g-1]>tmp)tmp=f[i-1][j][k-1][g-1]; if(f[i-1][j-1][k-1][g-1]>tmp)tmp=f[i-1][j-1][k-1][g-1]; f[i][j][k][g]=tmp+a[j][i-j+1]; if(j!=k)f[i][j][k][g]+=a[k][i-k+1]; if(g!=k && g!=j)f[i][j][k][g]+=a[g][i-g+1]; } } } } printf("%d",f[n+n-1][n][n][n]); return 0; }
法二：
网络流——最大费用最大流。
具体算法如下：
拆点建图，每一个点都拆成两个点，在这里就称为出点和入点。
出点和入点建两条边，一条费用为s[i][j]，流量为1；一条费用为0，流量为inf。（分别表示选择这个点和从这个点上经过）
将（i,j）的出点分别和（i+1,j）（i,j+1）的入点建边，流量为inf，费用为0。（表示行进）
跑一边最大费用最大流就可以了。
额~~~鼓掌鼓掌。
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<cstdlib> #include<algorithm> #include<queue> #include<stack> #include<ctime> #include<vector> #define inf (2e8) using namespace std; int n,m; int ans; struct node { int next,to,cost,cap; } edge[500001]; int size=1,head[20001],s[51][51]; void putin(int from,int to,int cap,int cost) { size++; edge[size].next=head[from]; edge[size].to=to; edge[size].cap=cap; edge[size].cost=cost; head[from]=size; } void in(int from,int to,int cap,int cost) { putin(from,to,cap,cost); putin(to,from,0,-cost); } void build() { int i,j; in(0,1,3,0);//源点和1建边 in(n*n*2,n*n*2+1,3,0);//末节点和汇点建边 for(i=1; i<=n; i++) { for(j=1; j<=n; j++) { in((i-1)*n+j,(i-1)*n+j+n*n,1,s[i][j]);//一条费用为s[i][j]，流量为1的边 in((i-1)*n+j,(i-1)*n+j+n*n,inf,0);//一条费用为0，流量为inf的边 if(i!=n)in((i-1)*n+j+n*n,i*n+j,inf,0); if(j!=n)in((i-1)*n+j+n*n,(i-1)*n+j+1,inf,0);//和连接点建边，注意一下临界条件 } } } int f[300001],pre[300001],vis[300001]; bool bfs(int src,int des) { int i; for(i=0; i<=n*n*2+1; i++) { f[i]=-1; vis[i]=0; } queue<int>mem; mem.push(src); f[src]=0; vis[src]=1; while(!mem.empty()) { int x=mem.front(); mem.pop(); vis[x]=0; for(i=head[x]; i!=-1; i=edge[i].next) { int y=edge[i].to; if(edge[i].cap&&f[y]<f[x]+edge[i].cost) { f[y]=f[x]+edge[i].cost; pre[y]=i; if(!vis[y]) { mem.push(y); vis[y]=1; } } } } if(f[des]==-1)return 0; else return 1; }//最大费用最大流，求的是最长路，因此初值为-1 void change(int src,int des) { int x=des,flow=2e8; while(x!=src) { flow=min(flow,edge[pre[x]].cap); x=edge[pre[x]^1].to; } x=des; while(x!=src) { ans+=flow*edge[pre[x]].cost; edge[pre[x]].cap-=flow; edge[pre[x]^1].cap+=flow; x=edge[pre[x]^1].to; } }//反过来修改每一条边的流量，并计算ans的值，edge[i^1]为edge[i]的反向边 void max_cost_flow(int src,int des) { while(bfs(src,des))change(src,des); } int main() { memset(head,-1,sizeof(head)); int i,j; scanf("%d",&n); for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d",&s[i][j]); build(); max_cost_flow(0,n*n*2+1); printf("%d",ans); return 0; }