又是我没见过的新 trick？
应该也有别的做法吧。
题目链接
题意
现在有 种球和 个盒子，第 种球有 个，第 个箱子里最多放 个球。
除此之外，第 个箱子里最多放
个第 种球。
求最多能放多少个球。
题解
这个问题看上去就可以流，但是显然会 T。
我们不妨把这个图建出来。
这张图共有
个点，分别为源点 ，汇点 ，代表第 种小球的点 ，以及代表第 个箱子的点 。
边也分为三种：
- 边 ，流量为 ；
- 边 ，流量为 ；
- 边 ，流量为 。
显然，直接跑是不行的。
众所周知，最大流与最小割相等，那么存不存在什么快速的方法，求出这张图的最小割呢？
为方便使用公式，我们首先定义 为左部点的集合，
为右部点的集合。
考虑枚举 中与源点 联通的点集 ，枚举 中与汇点 联通的点集 ，那么对于上述的三种边：
- 对于边 ，若 ，则需要割掉这条边，价值为
；
- 对于边 ，若 ，则需要割掉这条边，价值为
；
- 对于边 ，若
$x_iP
- y_jQ$，则需要割掉这条边，价值为 。
那么我们就可以将最小割的值用一个式子表示出来！ 不太好算，考虑枚举 的值。 考虑枚举
的值，那么前面关于 的部分可以使用
dp 计算。
后面的值，对于每一个
来说都是一个分段函数，也是容易计算的。
时间复杂度 。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
using namespace std;
using ll=long long;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
inline ll lread()
{
ll s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
ll prek[150001];
ll preb[150001];
ll dp[150001];
ll b[500001];
ll a[501];
int n,m,Lim;
int main()
{
n=read(),m=read(),Lim=(ll)n*(n+1)/2;
memset(dp,0x3f,sizeof(dp)),dp[Lim]=0;
for(int i=1;i<=n;i++)
{
a[i]=lread();
for(int j=0;j+i<=Lim;j++) dp[j]=min(dp[j],dp[j+i]+a[i]);
}
for(int j=1;j<=m;j++)
{
b[j]=lread();ll s=b[j]/j;
prek[1]+=j;
if(s<Lim) prek[s+1]-=j,preb[s+1]+=b[j];
}
ll ans=inf;
for(int i=0;i<=Lim;i++)
{
prek[i]+=prek[i-1],preb[i]+=preb[i-1];
ans=min(ans,dp[i]+prek[i]*i+preb[i]);
}
printf("%lld\n",ans);
return 0;
}
|
感谢观看！