提出 #45738074

---

ソースコード 拡げる

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e2 + 5;

int n, m;
vector<string> a(N);

struct Dinic{
    static constexpr ll Inf = 1e18;
    int n;
    struct Edge{
        int to; ll c;
        Edge(int to, ll c) : to(to), c(c) {}
    };
    vector<Edge> e;
    vector<vector<int>> g;
    vector<int> cur, h;
    Dinic(int n) : n(n), g(n+1) {}
 
    void addEdge(int x, int y, ll w){
        g[x].push_back(e.size());
        e.push_back({y, w});
        g[y].push_back(e.size());
        e.push_back({x, 0});
    }
 
    bool bfs(int s, int t){
        h.assign(n+1, -1);
        queue<int> q;
        h[s] = 0;
        q.push(s);
        while(!q.empty()){
            int p = q.front(); q.pop();
            for(auto id : g[p]){
                auto [j, c] = e[id];
                if(c > 0 && h[j] == -1){
                    h[j] = h[p] + 1;
                    if(j == t) return true;
                    q.push(j);
                }
            }
        }
        return false;
    }
 
    ll dfs(int i, int t, ll f){
        if(i == t) return f;
        ll r = f;
        for(int &ci = cur[i]; ci<g[i].size(); ci++){
            int id = g[i][ci];
            auto [j, c] = e[id];
            if(c > 0 && h[j] == h[i] + 1){
                ll tmp = dfs(j, t, min(r, c));
                e[id].c -= tmp;
                e[id ^ 1].c += tmp;
                r -= tmp;
                if(r == 0) return f;
            }
        }
        return f - r;
    }
 
    ll maxFlow(int s, int t){
        ll ans = 0;
        while(bfs(s, t)){
            cur.assign(n+1, 0);
            ans += dfs(s, t, Inf);
        }
        return ans;
    }
};


void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    
    int ans = inf;
    vector<vector<int>> b(n+1);

    auto check = [&](int x) -> bool {
        // 1 ~ n => n + 1 + t, 
        vector<int> t;
        for(int i=1; i<=n; i++) for(auto j : b[i]){
            if(j <= x) t.push_back(j);
            else break;
        }

        sort(t.begin(), t.end());
        t.erase(unique(t.begin(), t.end()), t.end());
        int cnt = t.size();

        Dinic flow(n + cnt + 5);
        int S = n + cnt + 1;
        int T = S + 1;

        for(int i=1; i<=n; i++) flow.addEdge(S, i, 1);
        for(int i=1; i<=n; i++){
            for(auto j : b[i]){
                if(j > x) break;
                auto it = lower_bound(t.begin(), t.end(), j) - t.begin() + 1;
                flow.addEdge(i, n + it, 1);
            }
        }
        for(int i=n+1; i<=n+cnt; i++) flow.addEdge(i, T, 1);
        auto mf = flow.maxFlow(S, T);
        return mf == n;
    };

    for(char c='0'; c<='9'; c++){
        for(int i=1; i<=n; i++) b[i].clear();
        bool ok = 1;
        for(int i=1; i<=n; i++){
            vector<int> tmp;
            for(int j=0; j<m; j++){
                if(a[i][j] == c){
                    // b[i].push_back(j);
                    tmp.push_back(j);
                }
            }
            if(tmp.empty()){
                ok = 0;
                break;
            }
            int ts = tmp.size();
            for(int k=0; k<n; k++){
                b[i].push_back(tmp[k % ts] + m * (k / ts));
            }
        }
        if(!ok) continue;

        // for(int i=1; i<=n; i++){
        //     int cur = 0;
        //     while(b[i].size() < n){
        //         b[i].push_back(b[i][cur] + m);
        //         cur++;
        //     }
        // }

        int ma = 0, mi = inf;
        for(int i=1; i<=n; i++){
            ma = max(ma, b[i].back());
            mi = min(mi, b[i][0]);
        }

        // if(c == '8'){
        //     for(int i=1; i<=n; i++){
        //         for(auto j : b[i]) cout << j << " ";
        //         cout << endl;
        //     }
        //     cout << "mi=" << mi << " ma=" << ma << endl;

        // }
        
        int l = mi, r = ma;
        while(l <= r){
            int mid = (l+r) >> 1;
            auto ok = check(mid);
            if(ok) r = mid - 1;
            else l = mid + 1;
        }

        ans = min(ans, l);
    }

    cout << (ans == inf ? -1 : ans) << endl;

}  


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    
    int t =1;
    //cin >> t;
    while(t--)
    solve();
    return 0;
}

提出情報

コンパイルエラー

Main.cpp: In member function ‘long long int Dinic::dfs(int, int, long long int)’:
Main.cpp:58:33: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   58 |         for(int &ci = cur[i]; ci<g[i].size(); ci++){
      |                               ~~^~~~~~~~~~~~

ジャッジ結果