Atcoder abc332

發表於 更新於 分類於 ， Disqus： 文章字數： 866 所需閱讀時間 ≈ 3 分鐘
G(网络流)

https://atcoder.jp/contests/abc332

G - Not Too Many Balls

n 种颜色的球，颜色i有ai个

m个盒子，第j个盒子最多放bj个球

此外 对于$(i\in[1,n],j\in[1,m])$, 盒子j最多放颜色i的球ij个

问所有盒子放的球的最大个数

n 500

m 5e5

ai,bj [0,1e12]

3s

1024mb

我的思路

这看起来就是 n个点表示颜色，m个点表示盒子

s->球，容量为ai表示这个颜色球最多这么多

球i->盒子j, 容量ij表示 (i,j)的限制

盒子->T 容量bj, 表示每个盒子的限制

这样flow(S,T)的值就是要求的结果

但是问题是 500*5e5 = 2.5e8 感觉会tle?

换一个角度如果把S,T去掉直接变成点分裂，那就是二分图最大匹配

二分图最大匹配从 过程的观点来看，就是有“反悔”的操作

题解

一样的建立图，也一样的直接dinic算法时间不够

但是这里变成考虑 最小割，因为众所周知 最小割=最大流

X=颜色点集

Y=盒子点集

$P\subseteq X$ 为在S一侧的 颜色集合

$Q\subseteq Y$为在S一侧的 盒子集合

所以这个割 为 S->(X-P)+X->(Y-Q) + Q->T 三部分, 这样的最大好处就是中间的边是 $\sum i \cdot \sum j$, 而不需要建立$nm$条边了

考虑 $k =\sum_{x_i\in P}i$的值在范围$[0,L=\frac{N(N+1)}{2}]$ 范围

$\displaystyle \min_{k\in[0,L]}\min_{P\subseteq X,(\sum_{x_i\in P}i) = k}\min_{Q\subseteq Y}\left( \sum_{x_i\in X - P}A_i+k\sum_{y_j\in Y-Q}j+\sum_{y_j\in Q} B_j \right)$

这样会发现 i和j之间独立开了，也就是具体i的选择 只影响第一项，而j的选择只影响后两项

$\displaystyle \min_{k\in[0,L]}\left(\min_{P\subseteq X,(\sum_{x_i\in P}i) = k}\sum_{x_i\in X - P}A_i+\min_{Q\subseteq Y}\left( k\sum_{y_j\in Y-Q}j+\sum_{y_j\in Q} B_j \right)\right)$

第一项 直接$O(n^3)$ dp随便算

第二三项，注意到 如果一个j在Q内贡献是 $B_j$,否则贡献$kj$, 而与i选择是独立的，所以j的贡献 直接取$\min(kj,B_j)$即可

$\displaystyle \min_{j\in Y}(kj,B_j)$

这就很简单了， 按照$\frac{B_j}{j}$ 排序，

1
2
3
for k = 0..n(n+1)/2:
	ans = min(ans, ansA[k] + ansB)
	update(ansB)

代码

https://atcoder.jp/contests/abc332/submissions/50068019

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>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)
const ll INF=0x3f3f3f3f'3f3f3f3f;
ll read(){ll r;scanf("%lld",&r);return r;}
void chmin(ll &a,ll b){a=min(a,b);};

ll a[510];
ll b[500010];
int main(){
  ll n=read(); // 500
  ll m=read(); // 5e5
  rep(i,1,n+1) a[i]=read();
  rep(i,1,m+1) b[i]=read();
  ll L = n*(n+1)/2;
  vector dp(L+1,INF);
  dp[0]=0;
  rep(i,1,n+1) per(v,0,L+1) if(dp[v] != INF) chmin(dp[v+i],dp[v]+a[i]);
  rep(i,0,L+1) {
    if(i > L-i) break;
    swap(dp[i],dp[L-i]);
  }
  vector<pair<ll,ll> > ib;
  rep(i,1,m+1) ib.push_back({i,b[i]});
  sort(begin(ib),end(ib),[&](const auto &v0,const auto&v1){
      auto [i0,b0] = v0;
      auto [i1,b1] = v1;
      return b0/i0 < b1/i1;
  });
  ll sumj = m*(m+1)/2;
  ll sumbj = 0;
  ll ans = INF;
  int itr = 0;
  rep(k,0,L+1){
    while(itr < (int)ib.size() and ib[itr].first * k >= ib[itr].second) {
      auto [j,bj] = ib[itr];
      sumbj += bj;
      sumj -= j;
      itr++;
    }
    chmin(ans,dp[k]+sumbj+sumj*k);
  }
  printf("%lld\n",ans);
  return 0;
}

总结

哦，对啊 最大流 反过来 求最小割，解决中间连接数量大的问题