ECR160-E Matrix Problem

問題

https://codeforces.com/contest/1913/problem/E (2400diff)

行列の01行列が与えられる。また、長さがそれぞれの数列が与えられる。

あなたの目標はのいくつかのマスを反転することで、 行目のの数を個、列目のの数をにすることである。

目標を達成することが可能なら、反転するマスの最小個数を、不可能ならそのことを報告せよ。

制約

• 

解法

が明らかに必要。

最小費用流の問題に帰着させる。各マスに0か1を割り当てることを考える。

• もともとのマスの値がのとき、を割り当てるのにコスト, を割り当てるのにコスト
• もともとのマスの値がのとき、「あらかじめ一回操作をして値をにした」と考える。を割り当てるのにコスト, を割り当てるのにコスト

負コストがあるので、初回のポテンシャル計算にはベルマンフォードを使う。最初ネットワークがDAGなので、dpをしても良い。

実装

#include <bits/stdc++.h>

#include "Src/Template/IOSetting.hpp"
#include "Src/Graph/Flow/SuccessiveShortestPath.hpp"
using namespace zawa;

int main() {
    SetFastIO();

    int n, m; std::cin >> n >> m;
    std::vector s(n, std::vector<int>(m));
    for (auto& v : s) for (auto& x : v) std::cin >> x;
    std::vector<int> a(n), b(m);
    for (auto& x : a) std::cin >> x;
    for (auto& x : b) std::cin >> x;
    int sum{std::reduce(a.begin(), a.end(), 0)};
    if (sum != std::reduce(b.begin(), b.end(), 0)) {
        std::cout << -1 << '\n';
        return 0;
    }
    SuccessiveShortestPath<int, int> mcf(n + m + 2);
    int source{n + m}, sink{source + 1};
    for (int i{} ; i < n ; i++) {
        mcf.addEdge(source, i, a[i], 0);
    }
    for (int i{} ; i < m ; i++) {
        mcf.addEdge(n + i, sink, b[i], 0);
    }
    int ans{};
    for (int i{} ; i < n ; i++) {
        for (int j{} ; j < m ; j++) {
            if (s[i][j] == 0) {
                mcf.addEdge(i, n + j, 1, 1);
            }
            else if (s[i][j] == 1) {
                ans++;
                mcf.addEdge(i, n + j, 1, -1); 
            }
            else {
                assert(false);
            }
        }
    }
    mcf.dagdp(source, sink);
    mcf.updatePotential();
    int flow{mcf.maxflow(source, sink)};
    assert(flow <= sum);
    if (flow < sum) {
        std::cout << -1 << '\n';
        return 0;
    }
    ans += mcf.minCost();
    std::cout << ans << '\n';
}

自分のMCFはACLより遅いが、ベルマンフォードやDAG上のDPでポテンシャルが計算できるのが強み(自慢)

反省

バチャ中はE問題を開くことが無かった。

自分にとってはDよりEの方が解きやすそうに見えた。

しかし、Dが解けていないなかでEのフローを信じて詰めれたかと言われると、かなり自信が無い。Dを解かないと始まらないな。