AtCoder Grand Contest #034 D問題 - Manhattan Max Matching

Source

AtCoder Grand Contest #034
問題文

問題概要

省略

解法

省略

cLay（version 20190608-1）のコード

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

int N, RC[1000], BC[1000];
ll RX[1000], RY[1000], BX[1000], BY[1000];
{
  int i, j, k;
  int node, st, ed;
  
  minCostFlow<int, ll> f;
  int flow; ll cost;
  
  rd(N,(RX,RY,RC)(N),(BX,BY,BC)(N));

  node = 2N+4;
  st = node++;
  ed = node++;
  f.malloc(node);

  rep(i,N){
    f.addEdge(st, i, RC[i], 0);
    f.addEdge(N+i, ed, BC[i], 0);
    f.addEdge(i, 2N+0, RC[i], 2d9-RX[i]-RY[i]);
    f.addEdge(i, 2N+1, RC[i], 2d9-RX[i]+RY[i]);
    f.addEdge(i, 2N+2, RC[i], 2d9+RX[i]-RY[i]);
    f.addEdge(i, 2N+3, RC[i], 2d9+RX[i]+RY[i]);
    f.addEdge(2N+0, N+i, BC[i], 2d9+BX[i]+BY[i]);
    f.addEdge(2N+1, N+i, BC[i], 2d9+BX[i]-BY[i]);
    f.addEdge(2N+2, N+i, BC[i], 2d9-BX[i]+BY[i]);
    f.addEdge(2N+3, N+i, BC[i], 2d9-BX[i]-BY[i]);
  }

  f.solve(st,ed,flow,cost);
  cost = (ll)4d9 * flow - cost;
  wt(cost);
}

Current time: 2024年04月26日08時06分06秒
Last modified: 2019年06月08日00時56分08秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC034 AGC_D
トップページに戻る

Logged in as: unknown user (not login)