Submission #70984926

---

Source Code Expand

#include <bits/extc++.h>

using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const ll INF = numeric_limits<ll>::max() / 4;

struct MCMF {
	struct edge {
		int from, to, rev;
		ll cap, cost, flow;
	};
	int N;
	vector<vector<edge>> ed;
	vi seen;
	vector<ll> dist, pi;
	vector<edge*> par;

	MCMF(int N) : N(N), ed(N), seen(N), dist(N), pi(N), par(N) {}

	void addEdge(int from, int to, ll cap, ll cost) {
		if (from == to) return;
		ed[from].push_back(edge{ from,to,sz(ed[to]),cap,cost,0 });
		ed[to].push_back(edge{ to,from,sz(ed[from])-1,0,-cost,0 });
	}

	void path(int s) {
		fill(all(seen), 0);
		fill(all(dist), INF);
		dist[s] = 0; ll di;

		__gnu_pbds::priority_queue<pair<ll, int>> q;
		vector<decltype(q)::point_iterator> its(N);
		q.push({ 0, s });

		while (!q.empty()) {
			s = q.top().second; q.pop();
			seen[s] = 1; di = dist[s] + pi[s];
			for (edge& e : ed[s]) if (!seen[e.to]) {
				ll val = di - pi[e.to] + e.cost;
				if (e.cap - e.flow > 0 && val < dist[e.to]) {
					dist[e.to] = val;
					par[e.to] = &e;
					if (its[e.to] == q.end())
						its[e.to] = q.push({ -dist[e.to], e.to });
					else
						q.modify(its[e.to], { -dist[e.to], e.to });
				}
			}
		}
		rep(i,0,N) pi[i] = min(pi[i] + dist[i], INF);
	}

	pair<ll, ll> maxflow(int s, int t) {
		ll totflow = 0, totcost = 0;
		while (path(s), seen[t]) {
			ll fl = INF;
			for (edge* x = par[t]; x; x = par[x->from])
				fl = min(fl, x->cap - x->flow);

			totflow += fl;
			for (edge* x = par[t]; x; x = par[x->from]) {
				x->flow += fl;
				ed[x->to][x->rev].flow -= fl;
			}
		}
		rep(i,0,N) for(edge& e : ed[i]) totcost += e.cost * e.flow;
		return {totflow, totcost/2};
	}

	// If some costs can be negative, call this before maxflow:
	void setpi(int s) { // (otherwise, leave this out)
		fill(all(pi), INF); pi[s] = 0;
		int it = N, ch = 1; ll v;
		while (ch-- && it--)
			rep(i,0,N) if (pi[i] != INF)
			  for (edge& e : ed[i]) if (e.cap)
				  if ((v = pi[i] + e.cost) < pi[e.to])
					  pi[e.to] = v, ch = 1;
		assert(it >= 0); // negative cost cycle
	}
};

#define int long long

const int N = 21;

int dp[(1 << N)+5];
int pr[(1 << N)+5];
int a[N];

signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    ///
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }
    if (sum%n != 0) {
        cout << "-1\n";
        return 0;
    }
    int rp = sum/n;
    MCMF fw(n+2);
    for (int i = 0; i < n; ++i) {
        a[i] -= rp;
        if (a[i] > 0) {
            fw.addEdge(n, i, a[i], 0);
        }
        if (a[i] < 0) {
            fw.addEdge(i, n+1, -a[i], 0);
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) if (a[i] > a[j]) {
            fw.addEdge(i, j, 1e10, 1);
        }
    }
    fw.maxflow(n, n+1);
    vector<array<int, 3>> res;
    for (int i = 0; i < n; ++i) {
        for (auto ed : fw.ed[i]) if (ed.to < n) {
            if (ed.flow > 0) {
                res.push_back({ed.from, ed.to, ed.flow});
            }
        }
    }
    cout << res.size() << '\n';
    int op = 0;
    while (op < res.size()) {
        for (auto& [aa, bb, cc] : res) {
            if (aa == -1) continue;
            if (a[aa]+rp < cc) continue;
            ++op;
            a[aa] -= cc;
            a[bb] += cc;
            cout << aa+1 << ' ' << bb+1 << ' ' << cc << '\n';
            aa = -1;
        }
    }
    
}

Submission Info

Compile Error

./Main.cpp: In function 'int main()':
./Main.cpp:141:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::array<long long int, 3> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |     while (op < res.size()) {
      |            ~~~^~~~~~~~~~~~

Judge Result