$\textbf{ABC247G}$

• 平面中有 $n$ 个点，坐标为 $(a_i,b_i)$，权值为 $c_i$。每一行每一列最多只能选一个点，最大化选点个数 $k$ 并输出。
• 同时对于 $i \in [1,k]$，最大化选出 $i$ 个点的权值和。
• $1 \le n \le 3 \cdot 10^4,1 \le a_i,b_i \le 150$。

对于一个点 $(x,y)$，如果选了它则第 $x$ 行第 $y$ 列都不能再选其它点，如果把第 $x$ 行向第 $y$ 列连边，这是一个二分图最大匹配模型。跑一遍最大流即可求出 $k$ 的值。

考虑第二问其实就是二分图最大权匹配，直接暴力跑 $k$ 遍费用流。令 $N = 300$，时间复杂度 $\mathcal O(N^3n)$，不知道能不能过。

使用 acl 的费用流，单次时间复杂度为 $\mathcal O(Nn \log n)$，总复杂度 $\mathcal O(N^2n\log n)$，可以通过。

#include<bits/stdc++.h>
#include <atcoder/all>
using ll = long long;
const int N = 5e5+5;
const ll inf = 1e10;
using namespace std;
using namespace atcoder;
int T,n,a[N],b[N],c[N],s,ss,tt,x;
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> a[i] >> b[i] >> c[i];
    auto build = [&](int lim){
        mcf_graph<int,ll> g(302);
        ss = 0,tt = 301;
        for(int i = 1;i <= 150;i ++) g.add_edge(ss,i,1,0),g.add_edge(i+150,tt,1,0);
        for(int i = 1;i <= n;i ++) g.add_edge(a[i],b[i]+150,1,inf - c[i]);
        return g.flow(ss,tt,lim);
    };
    cout << (x = build(1e9).first) << "\n";
    for(int i = 1;i <= x;i ++) cout << - build(i).second + inf * i << "\n";
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int V = 305;
const ll INF = 1e18;
struct Edge { int to, rev, cap; ll cost; };
vector<Edge> g[V];
ll dist[V];
int prv[V], pe[V];
void add(int u, int v, int cap, ll cost) {
    g[u].push_back({v, (int)g[v].size(), cap, cost});
    g[v].push_back({u, (int)g[u].size() - 1, 0, -cost});
}
void minc(vector<ll> &res) {
    int S = 0, T = 302;
    while (true) {
        fill(dist, dist + V, INF);
        dist[S] = 0;
        vector<bool> inq(V);
        queue<int> q;
        q.push(S); inq[S] = 1;
        while (!q.empty()) {
            int u = q.front(); q.pop(); inq[u] = 0;
            for (int i = 0; i < (int)g[u].size(); i++) {
                auto &e = g[u][i];
                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {
                    dist[e.to] = dist[u] + e.cost;
                    prv[e.to] = u; pe[e.to] = i;
                    if (!inq[e.to]) { q.push(e.to); inq[e.to] = 1; }
                }
            }
        }
        if (dist[T] >= INF / 2) break;
        ll cur = 0;
        for (int v = T; v != S; v = prv[v]) {
            auto &e = g[prv[v]][pe[v]];
            e.cap--; g[v][e.rev].cap++;
            cur -= e.cost;
        }
        res.push_back(res.empty() ? cur : res.back() + cur);
    }
}
int main() {
    int n; scanf("%d", &n);
    int best[151][151] = {};
    for (int i = 0; i < n; i++) {
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        if (c > best[a][b]) best[a][b] = c;
    }
    int S = 0, T = 302;
    for (int i = 1; i <= 150; i++) { add(S, i, 1, 0); add(i + 150, T, 1, 0); }
    for (int i = 1; i <= 150; i++)
        for (int j = 1; j <= 150; j++)
            if (best[i][j]) add(i, j + 150, 1, -best[i][j]);
    vector<ll> ans;
    minc(ans);
    printf("%d\n", (int)ans.size());
    for (ll x : ans) printf("%lld\n", x);
    return 0;
}