hdu2686Matrix && hdu3376 Matrix Again

この二つのテーマはデータの大きさが違う以外はそっくりだ.
問題の大意は1つのn*nの行列を与えて、yifenfeiは起点(1,1)のこの位置からずっと(n,n)まで数えて、1つの数を取り終わるたびに、次は現在の数の右方あるいは下の1つの数しか取れなくて、(2つの数の間の距離は1であるべきで、以前は下の方あるいは右方のいずれの数も取ることができると思っていた)、このように(n,n)まで取って、それから(n,n)から(1,1)を取り戻して、今回は1つの数を取るごとに、次は現在の数の左方か右方の1つの数しか取れず、最後に(1,1)に戻り、1つの数は1回しか取れず、このようにして取った後に取れる最大数を求める
この問題は最大費用最大ストリームで解くことができ、各数は1回しか取れないため、現在の各数に対して分割点を行い、iをiとi''に分割し、iから1つの辺をi''に接続し、容量は1で、費用はi番目の点の費用で、それからiとi点を取った後に取れる数を1つの辺に接続し、容量は1で、費用は0である.(1,1)->(n,n)->(1,1)からなので、スーパーソース点Sを確立し、Sと最初のノードを接続し、容量は2(2つのパスを歩くため)、費用は0、スーパーポイントTを確立し、接続点(n*n)''到T,容量为1,费用为0,然后求一次最大费用最大流流,因为1とn*nの2つの点を2回計算したので、彼らの費用の和を1回減算する必要があり、ネットワークフローのテーマ配列の大きさが重要であることが判明した.
注意:3376コード

#include <iostream>
using namespace std;
const int MAXN = 610*610*2+2;
const int MAXM = 4*MAXN;
const int inf = 1<<28;
struct node
{
       int from, to, next, value, cost;       
}mapp[MAXM];
int id;//         
int ffa[MAXN];//        
void init()
{
     id = 0;
     memset(ffa, -1, sizeof(ffa));     
}
void addedge(int u, int v, int w, int c)
{
     mapp[id].from = u, mapp[id].to = v, mapp[id].value = w, mapp[id].cost = c, mapp[id].next = ffa[u], ffa[u] = id ++;        
     
     mapp[id].from = v, mapp[id].to = u, mapp[id].value = 0, mapp[id].cost = -c, mapp[id].next = ffa[v], ffa[v] = id ++;        
}
int pre[MAXN];//           
int pos[MAXN];//               
int inque[MAXN];
int dist[MAXN];//         
int que[10*MAXM];
bool SPFA(int s, int e, int n)
{
     memset(pre, -1, sizeof(pre));
     memset(inque, false, sizeof(inque));
     for (int i = 0; i <= n; i ++){
         dist[i] = -inf;    
     }
     dist[s] = 0;
     int rear, front;
     rear = front = 0;
     que[rear ++] = s;
     inque[s] = true;
     pre[s] = s;// 
     while (front < rear){
           
           int pr = que[front ++];
           inque[pr] = false;
           for (int i = ffa[pr]; i != -1; i = mapp[i].next){
               int fro = mapp[i].from, to = mapp[i].to;
               if (mapp[i].value > 0 && dist[to] < dist[fro] + mapp[i].cost){
                  dist[to] = dist[fro] + mapp[i].cost;
                  pre[to] = fro, pos[to] = i;
                  if (!inque[to]){//
                     que[rear ++] = to;
                     inque[to] = true;
                  }
               }    
               
           }      
     }
     return (pre[e] != -1 && dist[e] > -inf);
}
int flow, cost;
int minCostflow(int s, int e, int n)
{
     
     flow = cost = 0;
     while (SPFA(s, e, n)){
           int min_flow = INT_MAX;
           for (int i = e; i != s; i = pre[i]){//             
               if (min_flow > mapp[pos[i]].value){
                  min_flow = mapp[pos[i]].value; 
               }
           }    
           if (!min_flow)continue;
           flow += min_flow;
           cost += dist[e];
           
           for (int i = e; i != s; i = pre[i]){
               mapp[pos[i]].value -= min_flow;
               mapp[pos[i]^1].value += min_flow;
           }
     }
     return cost;
} 
void pri(int n)
{
     for (int i = 1; i <= n; i ++){
         cout<<"i:"<<i<<endl;
         for (int j = ffa[i]; j != -1; j = mapp[j].next){
             if (mapp[j].value)
             cout<<mapp[j].to<<' '<<mapp[j].value<<' '<<mapp[j].cost<<endl;    
         }    
     }     
}
const int Go[2][2] = {{1, 0}, {0, 1}};
int n;
bool check(int x,int y)
{
     return (x > 0 && x <= n && y > 0 && y <= n);     
}
int mat[610][610];
int num[MAXN];
int main()
{
    //freopen("IN.txt", "r", stdin);
    //freopen("OUT.txt", "w", stdout);
    while (scanf("%d", &n) != EOF){
          init();
          
          int kao = 1;
          for (int i = 1; i <= n; i ++){
              for (int j = 1; j <= n; j ++){
                  scanf("%d", &mat[i][j]);
                  num[kao ++] = mat[i][j];    
              }    
          }
         /*for (int i = 1; i <= n*n; i ++){
              cout<<num[i]<<' ';
          }
          cout<<endl;*/
          for (int i = 1; i <= n*n; i ++){
              if (i == 1)addedge(i, i + n*n, 2, num[i]);
              else if (i == n*n) addedge(i, i + n*n, 2, num[i]);
                   else  addedge(i, i + n*n, 1, num[i]);
          }
          for (int i = 1; i <= n; i ++){
              for (int j = 1; j <= n; j ++){
                  //cout<<"j:"<<j<<endl;
                  for (int k = 0; k < 2; k ++){
                      //for (int l = 1; l <= n; l ++){
                          int xx = i + Go[k][0];
                          int yy = j + Go[k][1];
                          if (!check(xx, yy))continue;
                          //cout<<"("<<i<<","<<j<<")->("<<xx<<","<<yy<<")"<<endl; 
                          addedge((i-1)*n + j + n*n, (xx-1)*n + yy, 1, 0);    
                      //}
                  }
              }    
          }
          //pri(2*n*n+2);
          int s = 2*n*n + 1, t = 2*n*n + 2;
          addedge(s, 1, 2, 0);
          addedge(2*n*n, t, 2, 0);
          //
          printf("%d
", minCostflow(s, t, 2*n*n+2)-(mat[1][1]+mat[n][n]));
    }
    return 0;    
}