Atcoder abc214

發表於 更新於 分類於 ， Disqus： 文章字數： 2.9k 所需閱讀時間 ≈ 10 分鐘
G(排列,图,容斥,DP,环)H(scc,网络流,费用流)

G - Three Permutations

https://atcoder.jp/contests/abc214/tasks/abc214_g

给[1..N]的排列p和q

求多少个排列r 满足 r[i] != p[i] , r[i] != q[i], i = [0..N]

mod 1e9+7

限制

n 3000

题解

我的思路

如果只是给一个排列p

要找另一个排列r让每个位置对应不等(r[i] != p[i])

一个想法是, 把它直接按照p[i]的1到n重新排序

问题变成了 找r[i] != i的排列方案数

考虑长度n的和n-1之间变化

如果i放的n,而n放的i ,那么 去掉i和n, 方案数 为f(n-2)

n 有 n-1中交替放的方案, (n-1) f(n-2)

如果i放的n,而n放的不是i, 那么,交换i和n放的, 前n-1也合法, f(n-1)

f(n-1) 每个方案每个位置和n换, 贡献(n-1)f(n-1)

f(n) = (n-1)(f(n-1) + f(n-2))

f(1) = 0

f(2) = 1

f(3) = 2(1+0) = 2

那么对于两个序列

首先一样的思路按照p 来排序

那么变成 r[i] != q[i], r[i] != i

但因为q[i]的限制并不能 像上面那样转移

题解

如果对于每个位置,计算ri=pi或ri=qi的排列方案数,可以考虑容斥

假设 i1,i2,…ik, 对应的下标满足, ri=pi 或 ri=qi, 那么要计算所有r[i1],r[i2]..r[ik]的值方案

对于每个 i in i[1..k],在图中,我们增加一个(pi,qi)的边, 只需计算每条边分配给其一个端点的总数，以便没有两条不同的边共享一个分配给它的顶点。(意思就是边即是i, 而给边分配的点,即是r[i]的值, 不能共享点,意味着值不重复

(注意到 如果(pi,qi)链接的话, 只可能是 链 或 环,不可能出现分叉

对于每个联通分量考虑(除去孤立点和自环)

因为环之间两两不相关, 所以每一组i的选择答案 = 不同环的方案的乘积

我们对于一个K个点的环内, 选了k条边, 的方案数

当所有边被选(所有的i都有相等关系), 那么有2种方案

不是全部都选, 考虑把环剖成链讨论首尾是否选择

dp[i][j][s0=0/1/2][si=0/1/2] 表示前i条边,选择了j条, 且第一条是s0 状态,第i条是si状态的方案数

0: 未选择

1: 该边分配了左点

2: 该边分配了右点

状态转移

不选 dp[i][j][s0][0] = sum dp[i-1][j][s0][0..2]

向左 dp[i][j][s0][1] = sum dp[i-1][j-1][s0][0..1]

向右 dp[i][j][s0][2] = sum dp[i-1][j-1][s0][0..2]

这样最后长n的环选了k条链的总方案数 就是sum dp[n][k][s0][s1], 且 (s0 != 1 || s1 != 2)

记为circle[n][k]

如果gi 表示 指定了i个不合法的选择, 剩余的n-i个任意选(可以合法也可以不合法,但始终满足是排列)

那么 $ans = \sum_{i=0}^n (-1)^i(n-i)! g_i$

而gi也可以通过上面环的结果, 去做dp

f[i][k] = 前i个环指定了k个边 的方案数

f[i][k] = sum{f[i-1][k-t] * circle[sz[i]][t]} 前i个环指定了k个边 的方案数

于是把所有环剖成链连续放在数组上

g[i][j][s0][s1] = 前i边,指定分配了j条, i所在环的起始是s0,结束是s1的方案数, 这里也是把s0也与i做相关意义了

转移类似, 分别是跨环转移 和 环内转移

感觉这题还可以改控制最大环长, 但增大总长度, 变成矩阵乘法

代码

https://atcoder.jp/contests/abc214/submissions/33643608

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;

using mint = atcoder::modint1000000007;

#define rep(i,a,n) for (int i=a;i<(int)n;i++)

int read(){int r;scanf("%d",&r);return r;} // read

const int N = 3000;

int p[N+10];
int q[N+10];
int e[N+10]; // 单向边
int vis2[N+10]; // 每个环的结束位置 = 1, 例如环为 2 3 5, 那么 [2]=1,[2+3=5]=1,[5+5=10]=1, 自环结束位置=2
// 0 不分配, 1 分配左点, 2分配右点
mint g[N+10][N+10][3][3]; // [i][j][s0][si] 每个环剖成链以后,长度i的链 分配了j条, 当前环 首个点state 0, 最后一个点statei
mint fac[N+10]; // n!

int main() {
  int n=read();
  fac[0]=1;
  rep(i,1,n+1) fac[i]=fac[i-1]*i;
  rep(i,0,n) p[i] = read();
  rep(i,0,n) e[p[i]] = q[i] = read(); // 建立边 p,q => e
  { // e => vis2
    vector<bool> vis(n+1,false); // 点是否被访问
    int m = 0;
    rep(i,1,n+1) if(!vis[i]){
      if(e[i]==i) { // 自环
        vis2[++m]=2;
        continue;
      }
      for(int j=i;!vis[j];j=e[j]) {
        vis[j]=1;
        m++;
      }
      vis2[m]=1;
    }
  }
  g[0][0][0][0] = 1; // 初始状态
  vis2[0] = 1;       // 初始状态
  rep(i,0,n+1) rep(j,0,i+1){ // 剖成链, 前i个边, 指定j个不合法, 第i个点所在环首个点s0,第i个点s1状态
    if(vis2[i]) { // 环结束位置
      g[i][j][1][2] = 0; // 环首为向左环尾向右
      if(vis2[i]==2) g[i][j][1][1]=0; // 自环, 不选是一种, 选左和选右相同, 去掉一个
      rep(k,0,3) rep(l,0,3) { // i+1 是新的环
        auto v = g[i][j][k][l];
        g[i+1][j  ][0][0] += v; // 新环 本身与i 无关, 应该是1,这里相当于全部乘上前面的倍数
        g[i+1][j+1][1][1] += v;
        g[i+1][j+1][2][2] += v;
      }
    } else { // 环内
      rep(k,0,3) rep(l,0,3){
        auto v = g[i][j][k][l];
        g[i+1][j  ][k][0] += v;
        g[i+1][j+1][k][1] += ((l == 2) ? 0 : v); // 不能下一个向左 这一个向右
        g[i+1][j+1][k][2] += v;
      }
    }
  }

  mint res = 0;
  rep(i,0,n+1) {
    mint cnt = 0; // 方案数
    rep(j,0,3) rep(k,0,3) cnt += g[n][i][j][k];
    res += fac[n-i]*cnt*(i%2?-1:1); // 容斥
  }
  printf("%d",res.val());
  return 0;
}

H - Collecting

https://atcoder.jp/contests/abc214/tasks/abc214_h

有向图 N点, M边

xi个东西在点i上

k个人一个一个遍历graph

1开始, 遍历有限长度, 找最大可被收集的东西个数

限制

n2e5, m 2e5

k 10

xi [1..1e9]

4s

1024mb

题解

我的思路

显然 可以scc缩点, 然后问题变成 一个有向无环图

找k(<=10)条路径, 被经过的点的和最大

这没啥想法了

例如

a->b->c

a->b->d

a->e->d

a->e->f

一次选择的贪心 是否对全局也是最好的?

题解

果然也是先scc变成DAG

然后这里是最小费用流问题

  1. DAG每个点拆成out,in, 增加源S和汇T
  2. DAG中每个u, 增加 in[u] -> out[u], 流量1, 费用-valu, 以及无限(K)流量费用0
  3. DAG中(u,v)变成 out[u] -> in[v] , 流量无限(K), 费用0
  4. S -> in[1] 容量k, 费用0 ( 这里可以简化成去掉S, 1 作为S, 通过 in[1] -> out[1] 总容量k 来保证最大流 = K
  5. out[u] -> T 容量无限(k), 费用0

求min cost max flow , 答案乘上 -1

我看atcoder的库是可以限制最大流的求 mincost

然后这样做的话 代价有些是负的

办法是

  1. DAG中每个u, in[u] -> out[u], 流量1费用0, 流量无限(费用val[u])
  2. DAG中(u,v), out[u] -> in[v], 无限流量, 费用sum X[u+1..v-1]
  3. out[u] -> T, 无限流量, 代价sum X[u+1..N]

ans = s->t 流=K 的最小代价 - K * sum X

原理

本质上希望每个流的代价增加 sum X

那么整体形式就是 从 in[u0] -> out[u0] -> in[v1] -> out[v1] -> T

希望 每次到out[u] 的时候, 费用和的增量是 前缀和X[0..u], 这样每个 out[u] -> T, 只需要是X[0..n] - X[0..u] 即可

那么自然 out[u]-> in[v] -> out[v]

这一整段增加为 X[0..v] - X[0..u] // 保证拓扑序 来让它非负? atcoder的scc返回保证了逆向拓扑序!!

那么, 这里设计 in[v] -> out[v] 增加X[v]

所以 out[u] -> in[v] 增加 X[0..v] - X[0..u] - X[v]

它这个没有拓扑似乎也保证不了 cost非负?

保证的是没有负环!?

注意因为没有S所以 链增加的是 X[0..n] - X[0..start]

费用流 mcmf

费用流, 每个边有流量限制和每单位费用

最大流最小费 = 最短路

最大流最大费 = 最长路

满足正向单位费用的相反数 = 逆向单位费用

最小费用以流量的单价作为边权值跑最短路，注意因为不会有负环（否则费用是负无限大）所以用SPFA就可以了

如果增广路中出现了负环，那么在上一次选择中一定有一条更短的路径。(如果开始就有负环呢？ 那么它说明你图建错了

最小费用流, 就是在做最大流的时候, 把dfs改成 spfa, 而距离= 路径上单位cost代价之和

代码

https://atcoder.jp/contests/abc214/submissions/33655383

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
#include <bits/stdc++.h>
#include <atcoder/scc>
#include <atcoder/mincostflow>
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;} // read

int main() {
  int N = read();
  int M = read();
  int K = read();
  vector<int> A(M), B(M);
  atcoder::scc_graph graph(N); // 0-index 点
  rep(i,0,M){
    A[i] = read() - 1; // 0-index
    B[i] = read() - 1;
    graph.add_edge(A[i], B[i]);
  }
  const vector<vector<int>> scc = graph.scc(); // 连通块 atcoder的scc返回还保证了逆拓扑序
  const int V = scc.size(); // DAG节点个数
  vector<int> belongs(N); // [节点] = 所在块
  rep(i,0,V) for(int u : scc[i]) belongs[u] = i;
  vector<ll> X(V); // 新图每个点上的值
  rep(i,0,N) X[belongs[i]] += read();
  vector<ll> accum(V + 1, 0); // 前缀和
  rep(i,0,V) accum[i + 1] = accum[i] + X[i];

  atcoder::mcf_graph<int, ll> network(2 * V + 1); // in[1]变成 S, T = 2*V
  int S = 2*belongs[0];
  int T = 2*V;
  rep(i,0,V) {
    network.add_edge(2 * i, 2 * i + 1, 1, 0); // in[i] -> out[i], 容量1, 费用 -X[i] + X[i]
    network.add_edge(2 * i, 2 * i + 1, K, X[i]); // in[i] -> out[i], 容量K(无穷), 费用 0 + X[i]
    network.add_edge(2 * i + 1, 2 * V, K, accum[V] - accum[i + 1]); // out[i] -> T 费用 0 + All - X[0..i]
  }
  rep(i,0,M) {
    int u = belongs[A[i]];
    int v = belongs[B[i]];
    if (u != v) network.add_edge(2 * u + 1, 2 * v, K, accum[v] - accum[u + 1]); // out[u] -> in[v] , 容量k, 费用 0 + X[0..v] - X[0..u]
  }
  auto [maxflow, mincost] = network.flow(S,T,K/* 限流 */);
  printf("%lld\n",(accum[V] - accum[belongs[0]]) * K - mincost);
}

总结

G

容斥还是不熟 感觉这个式子需要记忆 $ans = \sum_{i=0}^n (-1)^i c_i$

然后这个排列会构成多个环感觉很常用虽然知道, 但是这里通过边表示i, 分配点表示取值还是没有想到, 感觉也是一种转化思路

然后环拆成链+两头也是很经典的方法了

实现上把 环变成链 再在数组上连续性, 去做dp的方法, 比多重再算g更神奇

另外这里递推贡献更新时没有保证正确性, 有的在处理时才修复正确性 比如[1][2] 和自环

H

网络流完全不会, 学了一手费用流, 看起来就是正常最大流 变了spfa和 路径cost和

atcoder 内置的scc 和mincostflow

1
2
#include <atcoder/scc>
#include <atcoder/mincostflow>

然后这个神奇的让 所有费用变正的 前缀和变化法 , 感觉其它地方似乎也能用

参考

官方题解

oi wiki 费用流