题面

有

N 种糖果，

M 个小孩子，第

i 种糖果有

A_i

Ai 个，第

i 个孩子不能有超过

B_i

Bi 个同种类型的糖果，第

i 个孩子的糖果总数不能超过

C_i

Ci 。

合理分配糖果，问能分配出去的最大糖果数。

≤

N,M\leq 2e5

N,M≤2e5 。

题解

不难想到，这就是最大流啊！

可是我们完全没法建图，更是跑不过。

那，模拟最大流？

您可以试试，不过我们这道题的正解是用最大流最小割定理。

最大流等于最小割，此题最大流不好求，我们就求最小割。

一共有三类边，一类是源点连向每种糖果的边，权值为

A_i

Ai ，第二类是糖果和孩子之间的连边，孩子的每条入边边权都是

B_i

Bi ，第三类是孩子连向汇点的边，边权为

C_i

Ci 。

我们割掉一些边使得源点到不了汇点，可以逐个考虑。首先，糖果之间的顺序不重要，我们先把糖果按

A_i

Ai 从小到大排个序，割掉的边一定是个前缀。我们枚举割掉多少边，对应就已经有多少种糖果和源点不连通了，剩下的糖果，设一共有

X 种，要保证割掉第二类或第三类边后不与汇点连通。由于我们知道每种糖果与每个孩子都是存在边的，因此剩下的就是对于每个小孩子，独立地选择是割掉自己连向汇点的边（

C_i

Ci），还是割掉从源点连过来的边（

⋅

X\cdot B_i

X⋅Bi），选两者的较小值。由于决策是关于

X 单向变化的（

X 小到一定程度就不割

C_i

Ci 了），我们可以预处理出每个孩子决策变化时的

X 值。

时间复杂度

(

log

⁡

)

O(n\log n)

O(nlogn) ，基排可以

(

)

O(n)

O(n) 。

CODE

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<ctime>

#include<queue>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define MAXN 200005

#define LL long long

#define DB double

#define ENDL putchar('\n')

#define lowbit(x) (-(x) & (x))

#define FI first

#define SE second

#define eps (1e-4)

#define BI bitset<MAXN>

LL read() {

	LL f=1,x=0;char s = getchar();

	while(s < '0' || s > '9') {if(s=='-')f = -f;s = getchar();}

	while(s >= '0' && s <= '9') {x=x*10+(s-'0');s = getchar();}

	return f*x;

}

void putpos(LL x) {

	if(!x) return ;

	putpos(x/10); putchar('0'+(x%10));

}

void putnum(LL x) {

	if(!x) putchar('0');

	else if(x < 0) putchar('-'),putpos(-x);

	else putpos(x);

}

inline void AIput(LL x,char c) {

	putnum(x); putchar(c);

}

int n,m,s,o,k;

LL a[MAXN],b[MAXN],c[MAXN];

vector<int> bu[MAXN];

int main() {

	n = read();m = read();

	for(int i = 1;i <= n;i ++) {

		a[i] = read();

	}

	sort(a + 1,a + 1 + n);

	LL sm = 0,sb = 0;

	for(int i = 1;i <= m;i ++) b[i] = read();

	for(int i = 1;i <= m;i ++) {

		c[i] = read();

		sm += c[i];

		int le = (int)max(0ll,(LL)n - (c[i]/b[i]));

		if(le <= 0) {

			sm -= c[i];

			sm += n*1ll*b[i];

			sb += b[i];

		}

		else bu[le].push_back(i);

	}

	LL ans = sm;

	for(int i = 1;i <= n;i ++) {

		sm -= sb;

		sm += a[i];

		for(int j = 0;j < (int)bu[i].size();j ++) {

			int y = bu[i][j];

			sm -= c[y]; sm += (n-i) *1ll* b[y];

			sb += b[y];

		}

		ans = min(ans,sm);

	}

	printf("%lld\n",ans);

	return 0;

}

巴特西

ARC125E - Snack （网络流）

题面

题解

CODE

最新文章

热门文章