题意：
给出一个n × n的矩阵，每个格子中有一个数字代表权值，找出从左上角出发到右下角的两条不相交的路径(起点和终点除外)，使得两条路径权值之和最大。
分析：
如果n比较小的话是可以DP的，但是现在n非常大，DP会超时的。
这个用费用流来求解：
因为每个点只能走一次，所以先拆点，两点之间连一条容量为1费用为对应格子权值的边，如果是起点或终点，因为要走两次，所以要连容量为2的边。
对于不同格子之间，如果能到达，连一条容量为INF，费用为0的边。
因为算法求的是最小费用，所以我们把每个格子的相反数当做费用去连边，最后再取相反数。
因为起点和终点容量为2，计算出来的最大权值重复计算了左上角和右下角的权值，所以答案应该再减去这两个数。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std; const int maxn = ;
const int maxnode = maxn * maxn * ;
const int maxm = + ;
const int INF = 0x3f3f3f3f; struct Edge
{
int from, to, cap, flow, cost;
int nxt;
Edge() {}
Edge(int u, int v, int cap, int f, int cost, int nxt):from(u), to(v), cap(cap), flow(f), cost(cost), nxt(nxt) {}
}; int ecnt;
Edge edges[maxm << ];
int head[maxnode]; void AddEdge(int u, int v, int cap, int cost)
{
edges[ecnt] = Edge(u, v, cap, , cost, head[u]);
head[u] = ecnt++;
edges[ecnt] = Edge(v, u, , , -cost, head[v]);
head[v] = ecnt++;
} int row;
int A[maxn][maxn]; int n;
int d[maxnode + ], p[maxnode + ], a[maxnode + ];
bool inq[maxnode + ]; bool SPFA(int s, int t)
{
memset(inq, false, sizeof(inq));
memset(p, -, sizeof(p));
memset(d, 0x3f, sizeof(d));
inq[s] = true;
d[s] = ;
a[s] = INF; queue<int> Q;
Q.push(s);
while(!Q.empty())
{
int u = Q.front(); Q.pop(); inq[u] = false;
for(int i = head[u]; ~i; i = edges[i].nxt)
{
Edge& e = edges[i];
int v = e.to;
if(e.flow < e.cap && d[u] + e.cost < d[v])
{
d[v] = d[u] + e.cost;
p[v] = i;
a[v] = min(a[u], e.cap - e.flow);
if(!inq[v]) { inq[v] = true; Q.push(v); }
}
}
} return d[t] != INF;
} int Mincost(int s, int t)
{
int flow = ;
int cost = ;
while(SPFA(s, t))
{
flow += a[t];
cost += d[t] * a[t];
int u = t;
while(u != s)
{
edges[p[u]].flow += a[t];
edges[p[u]^].flow -= a[t];
u = edges[p[u]].from;
}
}
return cost;
} int main()
{
while(scanf("%d", &row) == )
{
for(int i = ; i < row; i++)
for(int j = ; j < row; j++) scanf("%d", &A[i][j]); n = row * row;
int s = , t = n * - ;
ecnt = ;
memset(head, -, sizeof(head)); //build graph
for(int i = ; i < row; i++)
for(int j = ; j < row; j++)
{
int u = i * row + j;
int v = u + n;
int cap = ;
if(u == || u == n - ) cap++;
AddEdge(u, v, cap, -A[i][j]); int w;
if(i < row - )
{
w = u + row;
AddEdge(v, w, INF, );
}
if(j < row - )
{
w = u + ;
AddEdge(v, w, INF, );
}
} n <<= ;
printf("%d\n", -Mincost(s, t) - A[][] - A[row-][row-]);
} return ;
}
代码君