题意：给定一个n*n的矩阵，找一条路，从左上角到右下角再到左上角，每个点最多经过一次，求路径上的点的权值的最大和。
将矩阵中每个点拆点，点容量为1，费用为点权值的相反数。每个点向自己右侧和下侧的点连一条容量为1，费用为0的边。左上角为起点，右下角为终点，对起点终点分别额外加条容量为1，费用为0的边，然后跑最大流最小费用。输出费用的相反数即可。
#include<bits/stdc++.h> using namespace std; const int N=720005; const int M=7200050; const int INF=0x3f3f3f3f; struct Edge { int to,next; int c,f,w; Edge(){} Edge(int to_,int c_,int f_,int w_,int next_) { to=to_,c=c_,f=f_,w=w_,next=next_; } }edge[M<<1]; int head[N],tot; bool inq[N]; int d[N],p[N],a[N]; void init() { memset(head,-1,sizeof(head)); tot=0; } void addedge(int u,int v,int c,int w) { edge[tot]=Edge(v,c,0,w,head[u]), head[u]=tot++; edge[tot]=Edge(u,0,0,-w,head[v]),head[v]=tot++; } bool spfa(int s,int t,int& flow,int& cost) { memset(d,INF,sizeof(d)); memset(inq,false,sizeof(inq)); queue<int> Q; d[s]=0,inq[s]=true,a[s]=INF; Q.push(s); while(!Q.empty()) { int u=Q.front();Q.pop(); inq[u]=false; for(int i=head[u];~i;i=edge[i].next) { Edge& e=edge[i]; int v=e.to; if(e.c>e.f&&d[v]>d[u]+e.w) { d[v]=d[u]+e.w,p[v]=i; a[v]=min(a[u],e.c-e.f); if(!inq[e.to]) Q.push(e.to),inq[e.to]=true; } } } if(d[t]==INF) return false; flow+=a[t],cost+=d[t]*a[t]; for(int u=t;u!=s;u=edge[p[u]^1].to) { edge[p[u]].f+=a[t]; edge[p[u]^1].f-=a[t]; } return true; } void Mincost(int s,int t,int& flow,int& cost) { flow=cost=0; while(spfa(s,t,flow,cost)); } //============================================== int n; inline int id(int x,int y) { return x*n+y; } int main() { while(~scanf("%d",&n)) { init(); for(int i=0;i<n;i++) for(int j=0;j<n;j++) { int temp; scanf("%d",&temp); if(i==0&&j==0||i==n-1&&j==n-1) addedge(id(i,j),id(i,j)+n*n,1,0); addedge(id(i,j),id(i,j)+n*n,1,-temp); if(i<n-1) addedge(id(i,j)+n*n,id(i+1,j),1,0); if(j<n-1) addedge(id(i,j)+n*n,id(i,j+1),1,0); } int s=id(0,0),t=id(n-1,n-1)+n*n; int flow,cost; Mincost(s,t,flow,cost); printf("%d ",-cost); } }