专栏文章

题解：P1791 [国家集训队] 人员雇佣

PPengzt
P1791题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min2ue63
此快照首次捕获于
2025/12/01 19:39
3 个月前
此快照最后确认于
2025/12/01 19:39
3 个月前
查看原文

Problem

给定 NN 个元素 aia_i，你需要把它们分成两个集合 A,BA, B。对于一个划分方案，代价为：
(∑i∈Aai)+∑i∈A(∑j∈AEi,j−∑j∈BEi,j)\left(\sum_{i \in A} a_i\right) + \sum_{i\in A}\left(\sum_{j\in A} E_{i, j} - \sum_{j\in B} E_{i, j}\right)
求划分的最小代价。
N≤1000N\le 1000，Ei,j<231E_{i,j}<2^{31}，Ai<231A_i<2^{31}。

Sol

这种二选一的东西，不难想到最小割。令 si=∑jEi,js_i = \sum_{j} E_{i, j}。
对于 i∈[1,n]i \in [1, n]，连边 (S,i,si)(S, i, s_i)，(i,T,Ai)(i, T, A_i)。
对于 i∈[1,n],j∈[1,n]i \in [1, n], j \in [1, n]，连边 (i,j,2Ei,j)(i, j, 2E_{i, j})。
求最小割即可。

Code

远古代码，看看就好。
CPP
#include<bits/stdc++.h>
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define pb emplace_back
using namespace std;
int n;
int a[1010];
struct Flow {
	const ll inf = 1e18;
	int n, S, T;
	struct node {
		int v; ll w; int b;
		node(int _v, ll _w, int _b) {
			v = _v, w = _w, b = _b;
		}
	};
	vector < vector < node > > e;
	vi dis, cur, q;
	Flow(int _n) : e(_n + 10), dis(_n + 10), cur(_n + 10), q(_n + 10) {
		n = _n;
	}
	void adde(int u, int v, ll w) {
		e[u].pb(v, w, sz(e[v]));
		e[v].pb(u, 0, sz(e[u]) - 1);
	}
	int hd, tl;
	bool bfs() {
		for(int i = 0; i <= n; ++i) dis[i] = cur[i] = 0;
		q[hd = tl = 1] = S;
		dis[S] = 1;
		while(hd <= tl) {
			int u = q[hd++];
			for(auto i : e[u]) {
				int v = i.v;
				if(i.w && !dis[v]) {
					dis[v] = dis[u] + 1;
					q[++tl] = v;
					if(i.v == T) return 1;
				}
			}
		}
		return 0;
	}
	ll dfs(int u, ll flow) {
		if(u == T) return flow;
		ll res = 0;
		for(int &i = cur[u]; i < sz(e[u]); ++i) {
			int v = e[u][i].v;
			if(e[u][i].w && dis[v] == dis[u] + 1) {
				ll fl = dfs(v, min(flow, e[u][i].w));
				e[u][i].w -= fl, e[v][e[u][i].b].w += fl;
				flow -= fl, res += fl;
				if(!flow) return res;
			}
		}
		return res;
	}
	ll maxflow(int _S, int _T) {
		S = _S, T = _T;
		ll res = 0;
		while(bfs()) res += dfs(S, inf);
		return res;
	}
};
int main() {
	ios :: sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	int S = n + 1, T = n + 2;
	Flow G(T);
	for(int i = 1; i <= n; ++i)
		cin >> a[i],
		G.adde(i, T, a[i]);
	ll sum = 0;
	for(int i = 1; i <= n; ++i) {
		ll s = 0;
		for(int j = 1, x; j <= n; ++j) {
			cin >> x;
			s += x;
			G.adde(i, j, 2 * x);
		}
		G.adde(S, i, s);
		sum += s;
	}
	cout << sum - G.maxflow(S, T) << "\n";
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...