20. AtCoder-Dream Team

题目链接：Dream Team

经典费用流问题。超级源点 \(S\) 向每个 \(a\) 权值连流量为 \(1\)，费用为 \(0\) 的边，每个 \(b\) 权值向超级汇点 \(T\) 连流量为 \(1\)，费用为 \(0\) 的边，对于每个人 \(\lbrace a_i,b_i,c_i \rbrace\) 从 \(a_i\) 向 \(b_i\) 连流量为 \(1\)，费用为 \(-c_i\) 的边，跑最小费用最大流即可。

#include
#include 
#define pb push_back
#define endl '\n'
using namespace std;
using ll = long long;
const int maxn = 1e5 + 5;
const ll inf = 1e12;
int a[maxn], b[maxn], c[maxn];
void solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i)
    	cin >> a[i] >> b[i] >> c[i];
    vector ans;
    for (int k = 1; k <= 150; ++k) {
    	atcoder::mcf_graph g(305);
    	int s = 301, t = 302;
    	for (int i = 1; i <= 150; ++i) {
        	g.add_edge(s, i, 1, 0);
        	g.add_edge(i + 150, t, 1, 0);
    	}
    	for (int i = 1; i <= n; ++i) {
       		g.add_edge(a[i], b[i] + 150, 1, inf - c[i]);
    	}
        auto now = g.flow(s, t, k);
        if (now.first < k) 
            break;
        else 
            ans.push_back(inf * k - now.second);
    }
    cout << ans.size() << endl;
    for (auto i : ans) 
        cout << i << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}