[COGS 2051] 王者之剑题解网络流最大权闭合子图

【题目描述】#

saber 这是在阿尔托利亚·潘德拉贡成为英灵前的事情，她正要去拔出石中剑成为亚瑟王，在这之前她要去收集一些宝石。
宝石排列在一个n*m的网格中，每个网格中有一块价值为v(i,j)的宝石，阿尔托利亚·潘德拉贡可以选择自己的起点。
开始时刻为0秒。以下操作，每秒按顺序执行
1.在第i秒开始的时候，阿尔托利亚·潘德拉贡在方格（x,y）上，她可以拿走（x，y）中的宝石。
2.在偶数秒，阿尔托利亚·潘德拉贡周围四格的宝石会消失
3.若阿尔托利亚·潘德拉贡第i秒开始时在方格（x，y）上，则在第i+1秒可以立即移动到（x+1，y），（x，y+1），（x-1，y）或（x，y-1）上，也可以停留在（x,y)上。
求阿尔托利亚·潘德拉贡最多可以获得多少价值的宝石

【输入格式】#

第一行给出数字N,M代表行列数.N,M均小于等于100，宝石的价值不会超过10000.下面N行M列用于描述数字矩阵

【输出格式】#

输出最多可以拿到多少价值宝石

【样例输入】#

【样例输出】#

1
4

与网络流24题中方格取数相同
最大权闭合子图
黑白染色
相邻连INF的边
源点向白格子连格子权值的边
黑格子想汇点连权值的边

跑一遍最小割也就是最大流 Dinic解决

1
/*
2
 * @Author: WildRage
3
 * @Date: 2017-06-13 16:37:09
4
 * @Last Modified by:   WildRage
5
 * @Last Modified time: 2017-06-13 16:37:09
6
 */
7
#include<iostream>
8
#include<cstdio>
9
#include<cstring>
10
#include<queue>
11
using namespace std;
12
const int INF=0x7fffffff;
13
struct edge{
14
    int END,cap,next;
15
}v[500000];
16
int first[10005],p;
17
void add(int a,int b,int c){
18
    v[p].END=b;v[p].next=first[a];v[p].cap=c;first[a]=p++;
19
    v[p].END=a;v[p].next=first[b];v[p].cap=0;first[b]=p++;
20
}
21
int dis[10005];
22
bool vis[10005];
23
bool BFS(int S,int E){
24
    memset(vis,0,sizeof(vis));
25
    memset(dis,-1,sizeof(dis));
26
    queue<int> Q;
27
    Q.push(S);
28
    dis[S]=0;vis[S]=1;
29
    while(!Q.empty()){
30
        int u=Q.front();Q.pop();
31
        for(int i=first[u];i!=-1;i=v[i].next){
32
            if(!vis[v[i].END]&&v[i].cap>0){
33
                vis[v[i].END]=1;
34
                dis[v[i].END]=dis[u]+1;
35
                if(v[i].END==E)return 1;
36
                Q.push(v[i].END);
37
            }
38
        }
39
    }
40
    return 0;
41
}
42
int DFS(int x,int a,int E){
43
    if(x==E||a==0)return a;
44
    int flow=0,f;
45
    for(int i=first[x];i!=-1;i=v[i].next){
46
        if(dis[x]+1==dis[v[i].END]&&(f=DFS(v[i].END,min(a,v[i].cap),E))>0){
47
            v[i].cap-=f;
48
            v[i^1].cap+=f;
49
            flow+=f;
50
            a-=f;
51
            if(a==0)break;
52
        }
53
    }
54
    if(!flow)dis[x]=-1;
55
    return flow;
56
}
57
int Dinic(int S,int E){
58
    int flow=0;
59
    while(BFS(S,E)){
60
        flow+=DFS(S,INF,E);
61
    }
62
    return flow;
63
}
64
int a[105][105];
65
template<class T>inline void read(T &res){
66
  static char ch;T flag=1;
67
  while((ch=getchar())<'0'||ch>'9')if(ch=='-')flag=-1;res=ch-48;
68
  while((ch=getchar())>='0'&&ch<='9')res=(res<<1)+(res<<3)+ch-48;res*=flag;
69
}
70
int Main(){
71
    freopen("Excalibur.in","r",stdin);
72
    freopen("Excalibur.out","w",stdout);
73
    memset(first,-1,sizeof(first));
74
    int m,n;
75
    int sum=0;
76
    read(m),read(n);
77
    for(int i=1;i<=m;i++)
78
        for(int j=1;j<=n;j++){
79
            read(a[i][j]);
80
            sum+=a[i][j];
81
      }
82
    for(int i=1;i<=m;i++){
83
        for(int j=1;j<=n;j++){
84
            if((i&1)^(j&1)){
85
                add(0,n*(i-1)+j,a[i][j]);
86
                if(j-1>=1)add(n*(i-1)+j,n*(i-1)+j-1,INF);
87
        if(i-1>=1)add(n*(i-1)+j,n*(i-2)+j,INF);
88
        if(i+1<=m)add(n*(i-1)+j,n*(i)+j,INF);
89
        if(j+1<=n)add(n*(i-1)+j,n*(i-1)+j+1,INF);
90
            }
91
            else{
92
                add(n*(i-1)+j,n*m+1,a[i][j]);
93
            }
94

95
        }
96
    }
97
    return printf("%d",sum-Dinic(0,m*n+1));
98
}
99
int A=Main();
100
int main(){;}