题意：两遍最长路，不能走重复点。和UVA 10806类似。

分析：拆点，u->u'，MCMF，求的是最大流的最小费用，那么cost取负。

注意的是源点，源点不用拆，那么走出来的最小费用，左上角的点，右下角的点走了两遍，输出除去即可。

1 #include 
      
         2   3 using namespace std;  4   5 const int maxn = 2500+5;  6 const int INF = 0x3f3f3f3f;  7   8 struct Edge  9 { 10     int from, to, cap, flow, cost; 11 }; 12  13 struct MCMF 14 { 15     int n, m; 16     vector
       
         edges; 17     vector
        
          G[maxn]; 18     bool inq[maxn];         // 是否在队列中 19     int d[maxn];           // Bellman-Ford 20     int p[maxn];           // 上一条弧 21     int a[maxn];           // 可改进量 22  23     void init(int n) 24     { 25         this->n = n; 26         for(int i = 0; i < n; i++) G[i].clear(); 27         edges.clear(); 28     } 29  30     void AddEdge(int from, int to, int cap, int cost) 31     { 32         edges.push_back((Edge) 33         { 34             from, to, cap, 0, cost 35         }); 36         edges.push_back((Edge) 37         { 38             to, from, 0, 0, -cost 39         }); 40         m = edges.size(); 41         G[from].push_back(m-2); 42         G[to].push_back(m-1); 43     } 44  45     bool BellmanFord(int s, int t, int &flow, long long& cost) 46     { 47         memset(inq,0,sizeof(inq)); 48         for(int i=0;i
         

Q; 56 Q.push(s); 57 while(!Q.empty()) 58 { 59 int u = Q.front(); 60 Q.pop(); 61 inq[u] = false; 62 for(int i = 0; i < G[u].size(); i++) 63 { 64 Edge& e = edges[G[u][i]]; 65 if(e.cap > e.flow && d[e.to] > d[u] + e.cost) 66 { 67 d[e.to] = d[u] + e.cost; 68 p[e.to] = G[u][i]; 69 a[e.to] = min(a[u], e.cap - e.flow); 70 if(!inq[e.to]) 71 { 72 Q.push(e.to); 73 inq[e.to] = true; 74 } 75 } 76 } 77 } 78 if(d[t] == INF) return false; //s-t 不连通，失败退出 79 flow += a[t]; 80 cost += (long long)d[t] * (long long)a[t]; 81 int u = t; 82 while(u != s) 83 { 84 edges[p[u]].flow += a[t]; 85 edges[p[u]^1].flow -= a[t]; 86 u = edges[p[u]].from; 87 } 88 return true; 89 } 90 91 long long Mincost(int s, int t) 92 { 93 long long cost = 0; 94 int flow = 0; 95 while(BellmanFord(s, t, flow, cost)) { 96 if(flow==2) 97 break; 98 }; 99 return cost;100 }101 }sol;102 103 int maps[maxn][maxn];104 int aa[maxn*maxn];105 106 int main()107 {108 //freopen("in.txt","r",stdin);109 int n;110 while(scanf("%d",&n)!=EOF) {111 112 for(int i=0;i