方格取数

Time Limit: 5 Sec Memory Limit: 64 MB

Description

在一个n*n的方格里，每个格子里都有一个正整数。从中取出若干数，使得任意两个取出的数所在格子没有公共边，且取出的数的总和尽量大。

Input

第一行一个数n；接下来n行每行n个数描述一个方阵

Output

仅一个数，即最大和

Sample Input

2
　1 2
　3 5

Sample Output

6

HINT

n<=30

Main idea

给定一个矩阵，取了一个点就不能取上下左右的点了，求能取出的最大价值。

Solution

求的显然是最大权独立集，最大权独立集=总权-最小权覆盖集，对于最小权覆盖集我们用最小割来解。

由于取了一个点，不能取上下左右的点，即i±1 or j±1，那么显然是一个二分图，根据奇偶分类。

然后就是一个最小割的模型，我们左边的点向上下左右的点连边，容量为INF(必然不是割)，然后跑最大流即可。

Code

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
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;

const int ONE=1001;
const int TWO=100001;
const int INF=2147483640;

int n,m;
int tot=0;
int res,tou,wei,S,T;
int Dep[ONE],q[TWO],ans;
int a[ONE][ONE],PD[ONE][ONE],BI[ONE][ONE];
int next[TWO],first[TWO],go[TWO],w[TWO];
int E[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

int Add(int u,int v,int z)
{
    next[++tot]=first[u];   first[u]=tot;   go[tot]=v;  w[tot]=z;
    next[++tot]=first[v];   first[v]=tot;   go[tot]=u;  w[tot]=0;
}

int Bfs()
{
    memset(Dep,0,sizeof(Dep));
    q[1]=0;
    tou=0;  wei=1;  Dep[0]=1;
    for(int u=0;u<=n*n;u++) E[u]=first[u];
    while(tou<wei)
    {
        int u=q[++tou];
        for(int e=first[u];e;e=next[e])
        {
            int v=go[e];
            if(Dep[v] || !w[e])continue;
            Dep[v]=Dep[u]+1;
            q[++wei]=v;
        }
    }
    return (Dep[T]>0);
}

int Dfs(int u,int Limit)
{
    if(u==T || !Limit) return Limit;
    int flow=0,f;
    for(int &e=E[u];e;e=next[e])
    {
        int v=go[e];
        if(Dep[v]!=Dep[u]+1 || !w[e]) continue;
        f=Dfs(v,min(Limit,w[e]));
        w[e]-=f;
        w[e^1]+=f;
        Limit-=f;
        flow+=f;
        if(!Limit)break;
    }
    return flow;
}

void Build(int i,int j)
{
    if(BI[i-1][j])  Add(BI[i][j],BI[i-1][j],INF);
    if(BI[i][j-1])  Add(BI[i][j],BI[i][j-1],INF);
    if(BI[i+1][j])  Add(BI[i][j],BI[i+1][j],INF);
    if(BI[i][j+1])  Add(BI[i][j],BI[i][j+1],INF);
}

int main()
{
    n=get();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            a[i][j]=get();
            ans+=a[i][j];
            if( i%2!=j%2 ) PD[i][j]=1;
            BI[i][j]=++tot;
        }

    S=0;    T=n*n+1;    tot=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(PD[i][j]) Add(S,BI[i][j],a[i][j]);
            else Add(BI[i][j],T,a[i][j]);
            if(PD[i][j])    Build(i,j);
        }

    while(Bfs())
        res+=Dfs(0,INF);

    printf("%d",ans-res);
}