提出 #17416373

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

template <class T>
struct Dinic {
  struct edge {
    int to;
    T cap;
    int rev;
    edge(int t = 0, T c = 0, int r = -1) : to(t), cap(c), rev(r) {}
  };
  int n;
  T finf;
  vector<vector<edge>> g;
  vector<int> id;
  vector<int> d;
  Dinic(int _n = 1, T _finf = (int)(2e9))
      : n(_n), finf(_finf), g(n, vector<edge>()), id(n), d(n) {}

  int add(int start, int goal, T capacity) {
    g[start].emplace_back(goal, capacity, (int)g[goal].size());
    g[goal].emplace_back(start, 0, (int)g[start].size() - 1);
    return (int)g[start].size() - 1;
  }

  int change(int x, int idx, T newf, int s, int t) {
    int y = g[x][idx].to, ridx = g[x][idx].rev;
    newf -= g[x][idx].cap + g[y][ridx].cap;
    if (newf > 0) {
      g[x][idx].cap += newf;
      return solve(s, t);
    } else if (newf < 0) {
      g[x][idx].cap += newf;
      if (g[x][idx].cap >= 0) return 0;
      swap(newf = 0, g[x][idx].cap);
      g[y][ridx].cap += newf;
      newf += solve(x, y, -newf);
      if (-newf) {
        solve(x, s, -newf);
        solve(t, y, -newf);
      }
      return newf;
    }
    return 0;
  }

  void bfs(int st) {
    d.assign(n, -1);
    queue<int> qu;
    d[st] = 0;
    qu.push(st);
    while (qu.size()) {
      int now = qu.front();
      qu.pop();
      for (auto e : g[now])
        if (e.cap > 0 && d[e.to] < 0) {
          d[e.to] = d[now] + 1;
          qu.push(e.to);
        }
    }
  }
  T pathdfs(int now, int goal, T nf) {
    if (now == goal) return nf;
    int len = g[now].size();
    for (int& i = id[now]; i < len; ++i) {
      edge* e = &g[now][i];
      if (e->cap > 0 && d[now] < d[e->to]) {
        T res = pathdfs(e->to, goal, min(nf, e->cap));
        if (res > 0) {
          e->cap -= res;
          g[e->to][e->rev].cap += res;
          return res;
        }
      }
    }
    return 0;
  }
  T solve(int start, int goal, T flimit = 0) {
    if (!flimit) flimit = finf;
    T res = 0, nf = 0;
    while (flimit - res) {
      bfs(start);
      if (d[goal] < 0) return res;
      id.assign(n, 0);
      while ((nf = pathdfs(start, goal, flimit - res)) > 0) res += nf;
    }
    return res;
  }
};

int n, m;
vector<vector<int>> a, e;
vector<vector<vector<int>>> memo;
Dinic<int> din;

int main() {
  cin >> n >> m;
  a.resize(n, vector<int>(m, 0));
  e.resize(n, vector<int>(n, 0));
  memo.resize(n, vector<vector<int>>(n));
  din = Dinic<int>(2 * n + 2);
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      cin >> a[i][j];
      --a[i][j];
      memo[i][a[i][j] / m].push_back(a[i][j]);
    }
  for (int i = 0; i < n; ++i) {
    din.add(2 * n, i, 1);
    din.add(i + n, 2 * n + 1, 1);
    for (int j = 0; j < n; ++j) e[i][j] = din.add(i, j + n, memo[i][j].size());
  }
  din.solve(2 * n, 2 * n + 1);
  for (int i = 0; i < m; ++i) {
    vector<int> v(n, -1);
    for (int j = 0; j < n; ++j)
      for (auto [to, cap, rev] : din.g[j])
        if (to != 2 * n && cap != memo[j][to - n].size()) {
          a[j][i] = memo[j][to - n].back();
          memo[j][to - n].pop_back();
          v[j] = to - n;
          break;
        }
    for (int j = 0; j < n; ++j)
      din.change(j, e[j][v[j]], memo[j][v[j]].size(), 2 * n, 2 * n + 1);
  }
  for (auto v : a)
    for (int i = 0; i < m; ++i) cout << v[i] + 1 << " \n"[i == m - 1];
  for (int i = 0; i < m; ++i) {
    vector<int> v;
    for (int j = 0; j < n; ++j) v.push_back(a[j][i]);
    sort(v.begin(), v.end());
    for (int j = 0; j < n; ++j) a[j][i] = v[j];
  }
  for (auto v : a)
    for (int i = 0; i < m; ++i) cout << v[i] + 1 << " \n"[i == m - 1];
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:118:32: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  118 |         if (to != 2 * n && cap != memo[j][to - n].size()) {
      |                            ~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

ジャッジ結果