题意：两遍最长路，不能走重复点。和UVA 10806类似。
分析：拆点，u->u'，MCMF，求的是最大流的最小费用，那么cost取负。
注意的是源点，源点不用拆，那么走出来的最小费用，左上角的点，右下角的点走了两遍，输出除去即可。
#include <bits/stdc++.h> using namespace std; const int maxn = +;
const int INF = 0x3f3f3f3f; struct Edge
{
int from, to, cap, flow, cost;
}; struct MCMF
{
int n, m;
vector<Edge> edges;
vector<int> G[maxn];
bool inq[maxn]; // 是否在队列中
int d[maxn]; // Bellman-Ford
int p[maxn]; // 上一条弧
int a[maxn]; // 可改进量 void init(int n)
{
this->n = n;
for(int i = ; i < n; i++) G[i].clear();
edges.clear();
} void AddEdge(int from, int to, int cap, int cost)
{
edges.push_back((Edge)
{
from, to, cap, , cost
});
edges.push_back((Edge)
{
to, from, , , -cost
});
m = edges.size();
G[from].push_back(m-);
G[to].push_back(m-);
} bool BellmanFord(int s, int t, int &flow, long long& cost)
{
memset(inq,,sizeof(inq));
for(int i=;i<n;i++)
d[i] = INF;
d[s] = ;
inq[s] = true;
p[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 = ; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
if(e.cap > e.flow && d[e.to] > d[u] + e.cost)
{
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = min(a[u], e.cap - e.flow);
if(!inq[e.to])
{
Q.push(e.to);
inq[e.to] = true;
}
}
}
}
if(d[t] == INF) return false; //s-t 不连通，失败退出
flow += a[t];
cost += (long long)d[t] * (long long)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 true;
} long long Mincost(int s, int t)
{
long long cost = ;
int flow = ;
while(BellmanFord(s, t, flow, cost)) {
if(flow==)
break;
};
return cost;
}
}sol; int maps[maxn][maxn];
int aa[maxn*maxn]; int main()
{
//freopen("in.txt","r",stdin);
int n;
while(scanf("%d",&n)!=EOF) { for(int i=;i<n;i++)
for(int j=;j<n;j++)
scanf("%d",&maps[i][j]); int s = ,t = n*n-;
sol.init(n*n*); for(int i=;i<n;i++) {
for(int j=;j<n;j++) {
int id = i*n + j;
if(id!=s&&id!=t)
sol.AddEdge(id,id+n*n,,-maps[i][j]);
if(id==s) {
sol.AddEdge(id,id+,,);
sol.AddEdge(id,id+n,,);
}
else {
if(i<n-) sol.AddEdge(id+n*n,id+n,,);
if(j<n-) sol.AddEdge(id+n*n,id+,,);
}
}
} printf("%d\n",-sol.Mincost(s,t)+maps[][]+maps[n-][n-]); }
return ;
}