hdu 2686 Matrix最小費用の最大フロー

テーマリンク：http://acm.hdu.edu.cn/showproblem.php?pid=2686
Yifei very like Play a number game in the n*n Matrix.A positive integer number is put in each are a of the Matrix.
Every time yfreenfe i shound to is that chose a detour which from the top left point to the bottom Right point and than back to the top left point with the maximal values of sum integers and the the of Matrichoft thefrom the bottom to the top can only chose left and up.And yfreenfei can not pass the same ara of the Matrix except the start and end. 
 
n＊nの行列は、各数が正の整数であり、一番左上の位置から一番右下の位置まで歩くことが要求されています。毎回右または下の方に一マスしか歩けません。そして一番右下の位置から一番左上の位置に戻ります。毎回上または左に一マスだけ行くことができます。そして、この二つのパスの数を積算します。注意各格子は一回しか歩かない（一番左上と一番右下を除く）、つまりマトリクスの個数は一回だけ加算されます。
 
アルゴリズムの分析：この問題はDPを使ってもいいですが、DPは考え方が限られていますので、まだよく分かりません。
一番左上を源点とし、一番右下を為替点とする。上から下へ一度行って、下から上へ行くと、上から下へ二回行くのと同じです。つまり、ソースから送金ポイントまでの価値が一番大きくて、交わらない道を見つけます。
まず、（i-1）＊n＋j->（i-1）＊n＋j＋n＊n（wは1（注：ソースポイントとシンクポイントは2で、2つの道を見つけたいので）を外して、コストtはマトリックス中のこの値です。
(i-1)*n+j+n->(i-1)*n+j+1(wは1、cotは0)
（i-1）*n+j+n->i*n+j（wは1、cotは0）
そして費用の流れで解決すればいいです。（問題の中で明確に説明していますが、すべての数が正しいですか？私はdis[]関数が0 WAを初期化しました。これはなぜですか？）

  1 #include<iostream>

  2 #include<cstdio>

  3 #include<cstring>

  4 #include<cstdlib>

  5 #include<cmath>

  6 #include<algorithm>

  7 #include<vector>

  8 #include<queue>

  9 #define inf 0x7fffffff

 10 using namespace std;

 11 const int maxn=20000+10;

 12 const int M = 9999999;

 13 

 14 int n,from,to;

 15 struct node

 16 {

 17     int v,flow,cost;

 18     int next;

 19 }edge[M*3];

 20 int head[maxn],edgenum;

 21 int dis[maxn],pre[maxn],pid[maxn],vis[maxn];

 22 int an[33][33];

 23 

 24 void add(int u,int v,int flow,int cost)

 25 {

 26     edge[edgenum].v=v ;edge[edgenum].flow=flow;

 27     edge[edgenum].cost=cost ;edge[edgenum].next=head[u];

 28     head[u]=edgenum++;

 29 

 30     edge[edgenum].v=u ;edge[edgenum].flow=0;

 31     edge[edgenum].cost=-cost ;edge[edgenum].next=head[v];

 32     head[v]=edgenum++;

 33 }

 34 

 35 int spfa()

 36 {

 37     memset(vis,0,sizeof(vis));

 38     memset(dis,-1,sizeof(dis));

 39     queue<int> Q;

 40     Q.push(from);

 41     dis[from]=0;

 42     vis[from]=1;

 43     while (!Q.empty())

 44     {

 45         int u=Q.front() ;Q.pop();

 46         vis[u]=0;

 47         for (int i=head[u] ;i!=-1 ;i=edge[i].next)

 48         {

 49             int v=edge[i].v;

 50             if (edge[i].flow>0 && dis[v]<dis[u]+edge[i].cost)

 51             {

 52                 dis[v]=dis[u]+edge[i].cost;

 53                 pre[v]=u;

 54                 pid[v]=i;

 55                 if (!vis[v])

 56                 {

 57                     vis[v]=1;

 58                     Q.push(v);

 59                 }

 60             }

 61         }

 62     }

 63     return dis[to];

 64 }

 65 

 66 int mincost()

 67 {

 68     int aug=0,maxflow=0;

 69     int ans=0;

 70     int ncase=0;

 71     while (1)

 72     {

 73         aug=inf;

 74         int tmp=spfa();

 75         if (tmp==0) break;

 76         for (int i=to ;i!=from ;i=pre[i])

 77         {

 78             if (edge[pid[i] ].flow<aug)

 79                 aug=edge[pid[i] ].flow;

 80         }

 81         for (int i=to ;i!=from ;i=pre[i])

 82         {

 83             edge[pid[i] ].flow -= aug;

 84             edge[pid[i]^1 ].flow += aug;

 85         }

 86         ans += tmp;

 87         ncase++;

 88         if (ncase==2) break;

 89     }

 90     return ans-an[1][1]-an[n][n];

 91 }

 92 

 93 int main()

 94 {

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

 96     {

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

 98         edgenum=0;

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

100         {

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

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

103         }

104         from=1;

105         to=2*n*n;

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

107         {

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

109             {

110                 int u=(i-1)*n+j;

111                 int v=(i-1)*n+j+n*n;

112                 add(u,v,1,an[i][j]);

113                 if (j+1<=n) add(v,u+1,1,0);

114                 if (i+1<=n) add(v,i*n+j,1,0);

115             }

116         }

117         add(from,from+n*n,1,an[1][1]);

118         add(n*n,to,1,an[n][n]);

119         int sum=mincost();

120         printf("%d
",sum);

121     }

122     return 0;

123 }