Google Code Jam 2021 Round 2 4問目 - Retiling

Source

Google Code Jam 2021 Round 2 4問目 (11pts, 23pts)
問題文

問題概要

省略

解法

省略

cLayversion 20210405-1)のコード

C++に変換後のコードはこちら

int TEST;
int X, Y; ll F, S;
char A[10][12], B[10][12];
{
  int node, st, ed;
  dimcomp2 dm;
  minCostFlow<ll,ll> flow;
  flow.malloc(1d5);
  REP(TEST,rd_int()){
    ll res = 0, f, c;
    wtF("Case #{TEST+1}: ");
    rd(X,Y,F,S,A(X),B(X));
    node = X*Y;
    st = node++;
    ed = node++;
    dm.set(X,Y);
    flow.init(node);

    rep(i,X) rep(j,Y) if(A[i][j]=='M' && B[i][j]=='G') flow.addEdge(st, dm(i,j), 1, 0);
    rep(i,X) rep(j,Y) if(A[i][j]=='G' && B[i][j]=='M') flow.addEdge(dm(i,j), ed, 1, 0);
    rep(i1,X) rep(j1,Y) if(A[i1][j1]=='M' && B[i1][j1]=='G'){
      rep(i2,X) rep(j2,Y) if(A[i2][j2]=='G' && B[i2][j2]=='M'){
        flow.addEdge(dm(i1,j1), dm(i2,j2), 1, (abs(i1-i2) + abs(j1-j2)) * S - 2*F);
      }
    }

    rep(i,X) rep(j,Y) if(A[i][j] != B[i][j]) res += F;
    flow.solve(st, ed, f, c, -2, 0);
    wt(res + c);
  }
}

Current time: 2024年03月19日18時48分03秒
Last modified: 2021年05月16日08時47分47秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Google_Code_Jam GCJ_2021 GCJ_2021_Round_2
トップページに戻る

Logged in as: unknown user (not login)

ログイン: