ABC226 G: The baggage

atcoder.jp

公式解説とは異なる解法で解きました。

解法

荷物の重さの合計が体力の合計より大きいとき答えは明らかに No なので、以後、荷物の重さの合計は体力の合計以下であるとします。このとき、重さ 以上の荷物をすべて割り当てることができれば、重さ の荷物も必ず割り当てられるので、重さ 以上の荷物のみ考えます。

仮に重さ 以上の荷物がないと仮定すると、割り当てられる重さ の荷物の個数は最大で 個となります。この値を とおくと、重さ の荷物を割り当てることができるためには となればよいので、重さ 以上の荷物を加えていったときの の値を最大化すること、つまり の値の減少量を最小化することを考えます。

重さ 以上の荷物は 人につき 個しか持つことができません。重さ の荷物が体力 または の人に割り当てられたとき は 減少し、重さ の荷物が体力 の人に割り当てられたとき、また、重さ 以上の荷物がそれ以上の体力の人に割り当てられたとき、 は 減少します。よって、 の減少量の最小値は以下のように求めることができます。

• の 頂点からなる有向グラフを考え、以下のように辺を張ります。
  • 頂点 から にそれぞれ容量 、コスト の辺を張る。
  • 頂点 から と にそれぞれ容量 、コスト の辺を張る。
  • 頂点 から 、 から 、 から 、 から にそれぞれ容量 、コスト の辺を張る。
  • 頂点 から にそれぞれ容量 、コスト の辺を張る。
• このグラフ上で頂点 から に最小費用流を流します。流量が に等しい場合 の減少量の最小値はコストの合計値に等しく、満たない場合割り当ては不可能です。

実装

atcoder.jp

#include <bits/stdc++.h>
#include <atcoder/mincostflow>
using namespace std;
using namespace atcoder;
const long long INF = 1000000000000000000;
int main(){
  int T;
  cin >> T;
  for (int i = 0; i < T; i++){
    vector<long long> A(6);
    for (int j = 1; j <= 5; j++){
      cin >> A[j];
    }
    vector<long long> B(6);
    for (int j = 1; j <= 5; j++){
      cin >> B[j];
    }
    long long SA = A[1] + A[2] * 2 + A[3] * 3 + A[4] * 4 + A[5] * 5;
    long long SB = B[1] + B[2] * 2 + B[3] * 3 + B[4] * 4 + B[5] * 5;
    if (SA > SB){
      cout << "No" << endl;
    } else {
      long long cnt = B[2] + B[3] + B[4] * 2 + B[5] * 2;
      mcf_graph<long long, long long> G(8);
      G.add_edge(0, 1, A[3], 0);
      G.add_edge(0, 2, A[4], 0);
      G.add_edge(0, 3, A[5], 0);
      G.add_edge(1, 4, INF, 1);
      G.add_edge(1, 5, INF, 2);
      G.add_edge(1, 6, INF, 1);
      G.add_edge(2, 5, INF, 2);
      G.add_edge(2, 6, INF, 2);
      G.add_edge(3, 6, INF, 2);
      G.add_edge(4, 7, B[3], 0);
      G.add_edge(5, 7, B[4], 0);
      G.add_edge(6, 7, B[5], 0);
      pair<long long, long long> F = G.flow(0, 7);
      if (F.first < A[3] + A[4] + A[5]){
        cout << "No" << endl;
      } else {
        cnt -= F.second;
        if (A[2] > cnt){
          cout << "No" << endl;
        } else {
          cout << "Yes" << endl;
        }
      }
    }
  }
}