Atcoder abc326

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

https://atcoder.jp/contests/abc326

G -  Unlock Achievement

n个技能 初始等级1

m个成就

第$i$个成就需要 $\forall j, \mathrm{level_j} \ge L_{i,j}$ 就可达成，获得$A_i$奖励

而第i个技能的 每升级一级等级需要$C_i$代价

求最大 奖励减去代价

n,m 50

$L_{i,j} \leq 5$

$A_i,C_i\in [1,10^6]$

2s

1024mb

我的思路

如果确定了成就达成，那么对应的技能提升也就是 对应的技能等级的max

也就是给定了成就达成，需要O(NM) 完成计算 奖励减去代价

而注意到 ai都是正数，所以 如果指定了成就， 即使升级技能达成了额外成就，这样只会比当前的 结果更大，

如果 for 所有成就达成组合， ans=max(ans,计算代价()), 那么忽略额外达成的成就不会影响结果

然后发现这里没有用到的是 Li,j <= 5

然而似乎li,j = 1 or 2都没有特别的思路

如果n更小，且 lij被限制在1/2, 那么

可以dp[前i个成就][mask 技能] = 最大收入和

而n 现在范围有50,而且 lij 是[1,2,3,4,5] 所以 这种 状态会有

dp[前i个成就][技能需求state 5^n] = 最大收入和

1
5^50 = 88817841970012523233890533447265625
1
2^25 = 3355'4432

题解

最大流

如果你首先获得所有奖励

然后因为 未满足的成就失去奖励

点$S_{i,x}$表示技能i等级 大于等于x

点$T_j$表示 成就j

  • 对于$S_{i,1}$所有成立
  • 如果$S_{i,x}$成立 那么$C_i$会发生一次
  • 如果$S_{i,x}$未成立,那么$S_{i,x+1}$也不成立，也就是$S_{i,x}$不成立 且 $S_{i,x+1}$成立会产生无限大待阿鸡
  • $S_{k,L_{j,k}}$不成立 则 $T_j$不成立

问题变成 一堆点 成立或不成立, 是一个最小割问题!!!!!!!!! 做了好多次这样的，咋自己还是想不起来，哎

就是 源表示成立，汇表示不成立， 然后 割后的连通性表示 最终的选择

而 有 推导关系建立无限大的边，代价也建立边即可

代码

https://atcoder.jp/contests/abc326/submissions/49871943

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
#include <bits/stdc++.h>
#include<atcoder/maxflow>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
int main(){
  int n=read();
  int m=read();
  vector<int> c(n);
  rep(i,0,n) c[i]=read();
  vector<int> a(m);
  rep(i,0,m) a[i]=read();
  vector L(m,vector(n,0));
  rep(i,0,m) rep(j,0,n) L[i][j] = read()-1;
  ll ans = 0;
  rep(i,0,m) ans += a[i];
  // 5*n + m + S + T
  const int S=5*n+m;
  const int T=S+1;
  const ll INF = 50*1000000;
  atcoder::mf_graph<ll>g(T+1);
  auto skill=[&](int s,int lvl){return s*5+lvl;}; // lvl \in [0,5)
  auto achieve=[&](int i){return n*5+i;};
  // S连通表示不被选择, T连通表示被选择
  rep(i,0,n) {
    // g.add_edge(skill(i,0),T,INF); // 初始技能不被选择的代价INF
    rep(t,1,5) g.add_edge(S,skill(i,t),c[i]); // 技能等级达到的代价, 1级不需要额外代价
    rep(t,0,5-1) g.add_edge(skill(i,t),skill(i,t+1),INF); // 小未选择 & 大的选择
  }
  rep(i,0,m) g.add_edge(achieve(i),T,a[i]); // 成就不被选择的代价
  rep(i,0,m) rep(j,0,n) g.add_edge(skill(j,L[i][j]),achieve(i),INF);// 等级未达到&成就被选择
  printf("%lld\n",ans - g.flow(S,T));
  return 0;
}

总结

像这种 启动a => 启动多个b的 应该向网络流考虑了，要建立条件反射？？

成立/不成立的 -> 最小割， 应该离散的时间做了好多次，做了又忘，哎

比如 abc225g,abc259g,abc274g