OI - SurroundingGame(TopCoder) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - SurroundingGame(TopCoder)

发表于 分类于 Valine：

以前学过的内容，结果现在还是不会……

题面

有一个 $n\times m$ 的棋盘，你可以花费 $cost(i,j)$ 的代价在 $(i,j)$ 处放一颗棋子。

如果格子 $(i,j)$ 满足下面条件之一时，你可以得到 $value(i,j)$ 的收益：

  • $(i,j)$ 上有棋子；
  • $(i,j)$ 的所有相邻的格子上都有棋子。

求“收益减花费”的最大值。

数据规模 $n,m\le20$。

解析

分析题目，大概可以找到下面这些 0/1 变量：

  • 格子 $(i,j)$ 是否放格子，记为 $f(i,j)$；
  • 格子 $(i,j)$ 周围是否都有棋子，记为 $g(i,j)$；

假设我们可以不花费任何代价就获得全部收益，再计算最小的“额外损失=花费+损失收益”，即想到最小割模型——二元关系最小割。于是继续分析变量的联系。

这些变量的两两联系也有两类（这里的“联系”指两变量共同影响答案）

  • $f(i,j)$ 和 $g(i,j)$，额外损失表如下：
下 $f(i,j)$ \ 右 $g(i,j)$ 0 1
0 $value$ $0$
1 $cost$ $cost$
  • $g(i,j)$ 和相邻格子的 $f$，限制就是：如果 $g(i,j)=1$，则相邻格子的 $f$ 也为 $1$；可以表示为 $g(i,j)=1,f(邻)=0$ 的额外损失为 $+\infty$。

接下来就是建图，拿出二元关系最小割的模板，割左边表示选 $0$，割右边表示选 $1$：

png1

对于 $f(i,j)$ 和 $g(i,j)$ 的联系：

发现 $K=e+f=(3)+(4)-(1)-(2)=-value<0$，需要利用二分图的性质反向，则把 $g$ 的含义反转，即割 $c$ 表示选 $1$，割 $d$ 表示选 $0$。则新的方程为：

直接解方程可以得到一组较简单的解：$b=cost,f=value,a=c=d=e=0$。

对于 $g(i,j)$ 和相邻的 $f$ 的联系也可以列出方程：

仍然会发现 $K=-\infty<0$，再次利用二分图性质反向，但是 $g$ 已经反过向了，只能把 $f$ 反向——注意到方格图的相邻格子连边是天然的二分图，所以可以 $f$ 可以反转。得到的方程是

易得 $e=+\infty,a=b=c=d=f=0$。

最后整理得到流网络如下：

png2

源代码

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/*Lucky_Glass*/
#include<queue>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int N=405,M=N*6,INF=0x3f3f3f3f;
#define ci const int &

class SurroundingGame{
private:
    struct GRAPH{
        int head[N<<1],cap[M<<1],nxt[M<<1],to[M<<1],ncnt;
        GRAPH(){ncnt=1;}
        void AddEdge(ci u,ci v,ci varc){
            // printf("%d -> %d %d\n",u,v,varc);
            int p=++ncnt,q=++ncnt;
            to[p]=v,nxt[p]=head[u],head[u]=p,cap[p]=varc;
            to[q]=u,nxt[q]=head[v],head[v]=q,cap[q]=0;
        }
        inline int operator [](ci u){return head[u];}
    }Gr;
    int dep[N<<1],head[N<<1],St,Ed,n,m;
    inline int index(ci x,ci y,ci i){return 2*(x*m+y)+i;}
    bool BFS(){
        for(int i=1;i<=Ed;i++) dep[i]=-1,head[i]=Gr[i];
        queue<int> que;que.push(St),dep[St]=0;
        while(!que.empty()){
            int u=que.front();que.pop();
            for(int it=head[u];it;it=Gr.nxt[it]){
                int v=Gr.to[it];
                if((~dep[v]) || !Gr.cap[it]) continue;
                dep[v]=dep[u]+1;
                if(v==Ed) return true;
                que.push(v);
            }
        }
        return false;
    }
    int Aug(ci u,ci in){
        if(u==Ed) return in;
        int out=0;
        for(int &it=head[u];it;it=Gr.nxt[it]){
            int v=Gr.to[it];
            if(!Gr.cap[it] || dep[v]!=dep[u]+1) continue;
            int tov=Aug(v,min(in-out,Gr.cap[it]));
            out+=tov,Gr.cap[it]-=tov,Gr.cap[it^1]+=tov;
            if(in==out) break;
        }
        return out;
    }
    int Dinic(){
        int ret=0;
        while(BFS()) ret+=Aug(St,INF);
        return ret;
    }
    int charint(const char &c){
        if('0'<=c && c<='9') return c-'0';
        if('a'<=c && c<='z') return c-'a'+10;
        return c-'A'+36;
    }
    bool law(ci x,ci y){return 0<=x && x<n && 0<=y && y<m;}
public:
    int maxScore(vector<string> cost,vector<string> value){
        n=cost.size(),m=cost[0].length();
        St=n*m*2+1,Ed=St+1;
        const int DIR[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
        int ans=0;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++){
                if((i+j)&1){
                    Gr.AddEdge(St,index(i,j,1),charint(cost[i][j]));
                    Gr.AddEdge(index(i,j,1),index(i,j,2),charint(value[i][j]));
                    for(int k=0;k<4;k++){
                        int p=i+DIR[k][0],q=j+DIR[k][1];
                        if(law(p,q)) Gr.AddEdge(index(i,j,2),index(p,q,1),INF);
                    }
                }
                else{
                    Gr.AddEdge(index(i,j,1),Ed,charint(cost[i][j]));
                    Gr.AddEdge(index(i,j,2),index(i,j,1),charint(value[i][j]));
                    for(int k=0;k<4;k++){
                        int p=i+DIR[k][0],q=j+DIR[k][1];
                        if(law(p,q)) Gr.AddEdge(index(p,q,1),index(i,j,2),INF);
                    }
                }
                ans+=charint(value[i][j]);
            }
        return ans-Dinic();
    }
}test;

THE END

Thanks for reading!

> By 何日重到苏澜桥-Bilibili