累了就要写题解，近期总是被虐到没脾气。

来回最短路问题貌似也能够用DP来搞。只是拿费用流还是非常方便的。

能够转化成求满流为2 的最小花费。一般做法为拆点，对于 i 拆为2*i 和 2*i+1。然后连一条流量为1（花费依据题意来定） 的边来控制每一个点仅仅能通过一次。

额外加入source和sink来控制满流为2。

代码都雷同，以HDU3376为例。

#include <algorithm>

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <queue>

#include <cmath>

#include <stack>

#include <map>

#pragma comment(linker, "/STACK:1024000000");

#define EPS (1e-8)

#define LL long long

#define ULL unsigned long long

#define _LL __int64

#define INF 0x3f3f3f3f

#define Mod 6000007

using namespace std;

const int EDGE = 6000000,POINT = 730000;

struct E

{

    int Max,cost,v,next;

}edge[EDGE];

int head[POINT];

int Top;

void Link(int u,int v,int w,int cost)

{

    edge[Top].v = v;

    edge[Top].Max = w;

    edge[Top].cost = cost;

    edge[Top].next = head[u];

    head[u] = Top++;

}

int Map[610][610];

int dis[POINT],cur[POINT],flow[POINT];

bool mark[POINT];

void Updata(int site,int flow,int &cost)

{

    for(;cur[site] != -1; site = edge[cur[site]^1].v)

    {

        edge[cur[site]].Max -= flow;

        edge[cur[site]^1].Max += flow;

        cost += edge[cur[site]].cost * flow;

    }

}

queue<int> q;

int spfa(int S,int T,int &cost)

{

    memset(mark,false,sizeof(mark));

    memset(dis,INF,sizeof(dis));

    cur[S] = -1,dis[S] = 0,flow[S] = INF;

    q.push(S);

    int f,t;

    while(q.empty() == false)

    {

        f = q.front();

        q.pop();

        mark[f] = false;

        for(int p = head[f];p != -1; p = edge[p].next)

        {

            t = edge[p].v;

            if(edge[p].Max && dis[t] > dis[f] + edge[p].cost)

            {

                dis[t] = dis[f] + edge[p].cost;

                cur[t] = p;

                flow[t] = min(flow[f],edge[p].Max);

                if(mark[t] == false)

                {

                    mark[t] = true;

                    q.push(t);

                }

            }

        }

    }

    if(dis[T] == INF)

        return 0;

    Updata(T,flow[T],cost);

    return flow[T];

}

int Cal_Max_Flow_Min_Cost(int S,int T,int n)

{

    int temp,flow = 0,cost = 0;

    do

    {

        temp = spfa(S,T,cost);

        flow += temp;

    }while(temp);

    return cost;

}

inline int Cal(int x,int y,int n)

{

   return ((x-1)*n+y)*2-1;

}

int main()

{

    int n;

    int i,j;

    while(scanf("%d",&n) != EOF)

    {

        memset(head,-1,sizeof(head));

        Top = 0;

        for(i = 1;i <= n; ++i)

        {

            for(j = 1;j <= n; ++j)

            {

                scanf("%d",&Map[i][j]);

                if(i == j && (i == 1 || i == n))

                    Link(Cal(i,j,n),Cal(i,j,n)+1,2,-Map[i][j]);

                else

                    Link(Cal(i,j,n),Cal(i,j,n)+1,1,-Map[i][j]);

                Link(Cal(i,j,n)+1,Cal(i,j,n),0,Map[i][j]);

            }

        }

        for(i = 1;i <= n; ++i)

        {

            for(j = 1;j <= n; ++j)

            {

                if(j < n)

                {

                    Link(Cal(i,j,n)+1,Cal(i,j+1,n),1,0);

                    Link(Cal(i,j+1,n),Cal(i,j,n)+1,0,0);

                }

                if(i < n)

                {

                    Link(Cal(i,j,n)+1,Cal(i+1,j,n),1,0);

                    Link(Cal(i+1,j,n),Cal(i,j,n)+1,0,0);

                }

            }

        }

        printf("%d\n",-Cal_Max_Flow_Min_Cost(1,n*n*2,n*n*2) - Map[1][1] - Map[n][n]);

    }

    return 0;

}