Atcoder abc347

發表於 更新於 分類於 ， Disqus： 文章字數： 1.8k 所需閱讀時間 ≈ 6 分鐘
G(project_selection_problem)

https://atcoder.jp/contests/abc347

G - Grid Coloring 2

n * n

a[i][j] \in [0,5]

可以把0改为 1~5

所有操作后

代价=4临的差的平方和

求 最小代价的具体方案

n 20

2s

1024mb

我的思路

一个是插头dp 但是边界状态是 $5^n$

不知道怎么利用15,因为只关心差，可以变换成 `-22`但没感觉有什么帮助

有想网络流，但是不知道怎么表示 选与代价的关系。

$(x-y)^2=x^2-2xy+y^2$ 感觉就是这个2xy不知道怎么处理

题解

首先 显然不会有不改的(是)

$\min _ {B\in\lbrace{1,2,3,4,5}\rbrace ^ {\lbrace1,2,\ldots,N\rbrace ^ 2}}\sum _ x\theta _ x(B _ x)+\sum _ {x\lt y}\phi _ {x,y}(B _ x,B _ y)$

这里 $x$和$y$都是坐标,$x<y$表示$x$的坐标的字典序更小

$\theta _ x(b)=\begin{cases}0&\quad(A _ x=0\vee b = A _ x)\\+\infty&\quad(\text{otherwise.})\end{cases}$

$\phi _ {x=(i,j),y=(k,l)}(b _ 1,b _ 2)=\begin{cases}0&\quad(\vert i-k\vert+\vert j-l\vert\neq1)\\ (b _ 1-b _ 2) ^ 2&\quad(\text{otherwise.})\end{cases}$

那么对于所有$x,y$ $\phi(x,y)$是一个 Monge array(蒙赫阵列)???

没有看懂这个 $\theta \phi$和后面建网络流有什么关系?

建图

果然 1,2,3,4,5的选择问题，变成了 >=1,>=2,>=3,>=4,>=5的选择

因为选1,2,3,4,5是互斥的，而>=是依赖关系，这个在之前做2-sat的时候有遇到过类似的处理

example

$S\to x_{\ge k}\to T$，$S\to x_{\ge k} \to \cdots \to y_{\ge j}\to T$的形式

那么 和$S$切断表示不满足，和T切断表示满足

  • $x_{\ge k+1}\to x_{\ge k}$有$+\infty$边, 依赖关系显然
  • 对于$A_x\neq 0$
    • $A_x > 1$ 则$S\to x_{\ge A_{x}}$ 有$+\infty$边，
    • $A_x < 5$,则$x_{\ge A_x+1}\to T$有$+\infty$边

![[Pasted image 20240908142502.png]]

1
2
3
4
5
6
7
8
9
// 例如这里 容量全是+\infty
A_x = 3
S--------------|
               |
               v
>=5 -> >=4 -> >=3 -> >=2 -> >=1
        |
        |
        --------------------->T

其实根据 定义 割断S表示不满足，割断T表示满足

这里的构图保证了 >=3,>=2,>=1不会和S割断, >=5, >=4,不会和T割断

这里发现 >=1始终需要满足，所以始终需要和T割断，又不直接产生代价 所以 >= 1连一条 容量0到T的边，因此 所有>=1的点也可以删除

然后上面的 图如果难理解还(根据割的意义)可以再画成这样， 然后发现0和前后缀的 infty容量是可以省略的

1
2
3
4
5
6
7
8
9
10
11
12
13
// 例如这里 容量全是+\infty
A_x = 3
                S
                |
  0      0    +infty +infty +infty
                |
                v
 >=5 -> >=4 -> >=3 -> >=2 -> >=1
                |
+infty +infty   0      0      0
                |
                v
                T

对于相邻格子$x,y$

  • $x_{\ge k} \to y_{\ge k}$ 容量$1$
  • $x_{\ge k} \to y_{\ge l}, (l<k)$ 容量$2$

这就很妙了 $k^2=1+3+\cdots+(2k+1)$

这个图是透明度的背景差评

这是有点反向解释了，如果正向思考怎么想

首先 还是根据而最开始的最小割的想法

和S属于 同一块的（不一定相连S只保证割断T） 表示满足

和T属于 同一块的（不一定相连T只保证割断S） 表示不满足

那么 相邻块的可以割断的点就是 x的满足的点 到 y的不满足的点 的边

$A_x=4,A_y=1$

$x_{\ge 1},x_{\ge 2},x_{\ge 3},x_{\ge 4}$ 到 $y_{\ge 2},y_{\ge 3},y_{\ge 4},y_{\ge 5}$ (这里的对称面是$y_{\ge{1}}$和$x_{\ge 5}$ 而这个不会有产出)

这里指标性的是$x_{\ge 4}$和$y_{\ge 2}$

有 $(j-i)^2 =$ 统计$(a,b)$的个数，其中$a,b\in[i+1,j]$

$=(a,a), a\in[i+1,j]$的个数+$2 \cdot (a,b),i<a<b\le j$的个数

那么 (a,a)就是 $x_{\ge k}\to y_{\ge k}$的边, 权重1

那么 (a,b),a<b就是 $x_{\ge k}\to y_{\ge (<k) }$的边, 权重2

所以这里会 再次发现，$x_{\ge 1}$始终都是多余的，可以直接不要这种点

这里让我感觉 不对劲的就是 这些0点，为啥 没有直接的S,T相连

实际上可以看成有相连但是 容量为0，那这样切割会导致 少计算吗？

其实是不会的，因为相邻点之间 会根据值切割，反过来说 如果相邻点不被切割，那么它们，要么同属于S,或同属于T 和具体取值产生了一一对应。

最后来统计点数, S,T, 4 * n * n个点

边

N * N * 4 内部v+1 -> v的约束

列j和j+1的相邻 N * (N-1) * 2 * (1+2+3+4)

最后是默认非零的点 点数 * (1 or 2), 这里如果想要边数量固定是2,那么需要加上 >=1 和 >= 6, 不过这两种点对于割的贡献为0,

代码

https://atcoder.jp/contests/abc347/submissions/57577620

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
#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++)
#define per(i,a,n) for (ll i=n;i-->(ll)(a);)

ll read(){ll r;scanf("%lld",&r);return r;}

int main() {
    using namespace std;
    int N=read();

    atcoder::mf_graph<int> G(1 + 4 * N * N + 1);
    const int S = 0, T = 1 + 4 * N * N;
    // v \in [1,4], A[i][j] > v
    const auto _{[N](int i, int j, int v){ return (i * N + j) * 4 + v; }};

    constexpr int inf = 2 * 20 * 19 * 16 + 1; // Let inf a value greater than maximum possible cos

    // Aij > v+1 则 Aij > v
    rep(i,0,N) rep(j,0,N) rep(v,1,4) G.add_edge(_(i, j, v + 1), _(i, j, v), inf);

    // j 和 j+1相邻
    rep(i,0,N) rep(j,0,N-1) rep(v,1,5) {
      G.add_edge(_(i, j    , v), _(i, j + 1, v), 1); // v=v
      G.add_edge(_(i, j + 1, v), _(i, j    , v), 1);
      rep(u,1,v) { // v > u
        G.add_edge(_(i, j    , v), _(i, j + 1, u), 2);
        G.add_edge(_(i, j + 1, v), _(i, j    , u), 2);
      }
    }

    // i和i+1相邻
    rep(i,0,N-1) rep(j,0,N) rep(v,1,5) {
      G.add_edge(_(i    , j, v), _(i + 1, j, v), 1); // v=v
      G.add_edge(_(i + 1, j, v), _(i    , j, v), 1);
      rep(u,1,v){ // v > u
        G.add_edge(_(i    , j, v), _(i + 1, j, u), 2);
        G.add_edge(_(i + 1, j, v), _(i    , j, u), 2);
      }
    }

    // 默认非零的点增加值限制
    rep(i,0,N) rep(j,0,N){
      int A=read();
      if(A == 0) continue;
      if(A < 5) G.add_edge(_(i, j, A), T             , inf); // 保证 不满足 > A
      if(A > 1) G.add_edge(S         , _(i, j, A - 1), inf); // 保证 满足 > A-1 也就是>=A
    }

    // 最大流=最小割
    G.flow(S, T);
    // https://github.com/atcoder/ac-library/blob/master/atcoder/maxflow.hpp
    // min_cut 实现原理是dfs+有剩余容量可达性, 判断是否和S可达, 返回的是 [点]=是否可达
    const auto& cut{G.min_cut(S)};

    rep(i,0,N) {
      rep(j,0,N){
        int B{1};
        rep(v,1,5) B += cut[_(i, j, v)];
        printf("%d ",B);
      }
      printf("\n");
    }
    return 0;
}

参考

https://atcoder.jp/contests/abc347/editorial/9689

(This is the generation of so-called Project Selection Problem for k-ary variables. Detailed explanation (in Japanese) can be found in articles by tokoharu-sakura and another by noshi91.)

[Tutorial, Flows] Project Selection Problem

project_selection_problem 笔记

总结

总觉得这种依赖的选择转化成图论，之前有做过，所以也有向图论方向想，但是没有这样系统的学一下Project selection problem,感觉又会了一点点。

上面的$\theta,\phi$的作用是, 由$\theta$来负责选定，而$\phi$是不关心 $A_x$与$b$是否相等的

这个拆平方是真没学会，好像见过，又好像没有

所以感觉最神奇的到头来 还是这个平方，前面的 图论转化 和 >= 转化 应该都能自己想到的

另外之前有很多次 最小割=最大流，但好像之前都是求容量，第一次用min_cut计算和S的连通性