头部背景图片
Decaku 's Blog |
Decaku 's Blog |

Hdu1569 洛谷P2774方格取数 状压dp or 最小割

描述:

给一个$n*m$的方格,每个格子里有个正数,要求选择若干数,这些数所在方格不能有相邻的边,要求选择的数的和最大。


思路:

状压dp玄学爆过去了,然而复杂度算下来不对。

正解是网络流。对方格染色,把方格变成二分图,把所有点的权相加,去掉最小割就是我们所要的答案了,所以具体的建图方式为:源点与黑色点连,汇点与白色点连,容量都是点权。然后又因为选了一个点以后会影响它相邻的点,这些边是不会出现在割集中的,所以把这些边的容量置inf。


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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=15000;
const int maxm=50000;
const int inf=1e9;
int cnt=-1,n,m,s,t,sum;
int head[maxn],dep[maxn],cur[maxn];
struct P
{
int id,w;
};
vector<P>_1,_2;
struct Edge
{
int next=-1;
int to,w;
} edge[maxm*2];

void add_edge(int u,int v,int w)
{
//cout<<u<<" "<<v<<" "<<w<<endl;
edge[++cnt].next=head[u];
edge[cnt].to=v;
edge[cnt].w=w;
head[u]=cnt;
}
bool bfs()
{
queue<int>que;
while(!que.empty())que.pop();
memset(dep,0,sizeof(dep));
dep[s]=1;
que.push(s);
while(!que.empty())
{
int u=que.front();
que.pop();
for(int i=head[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].to;
if(!dep[v]&&edge[i].w)
{
dep[v]=dep[u]+1;
que.push(v);
}
}
}
if(dep[t]>0)
return 1;
return 0;
}
int dfs(int u,int flow)
{
if(u==t) return flow;
for(int &i=cur[u]; i!=-1; i=edge[i].next)
{
int v=edge[i].to;
if((dep[v]==dep[u]+1)&&edge[i].w)
{
int d=dfs(v,min(flow,edge[i].w));
if(d>0)
{
edge[i].w-=d;
edge[i^1].w+=d;
return d;

}
}
}
return 0;
}
int Dinic()
{
int ans=0;
while(bfs())
{
for(int i=1; i<=n*m+2; i++)
cur[i]=head[i];
while(int d=dfs(s,inf))
{
ans+=d;
}
}
return ans;
}



int main()
{
//1-n*n n*n+1,n*n+2m
while(~scanf("%d %d",&n,&m))
{
_1.clear();
_2.clear();
sum=0;
memset(head,-1,sizeof(head));
cnt=-1;
s=n*m+1;
t=n*m+2;
int _cnt=0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
P tem;
scanf("%d",&tem.w);
sum+=tem.w;
_cnt++;
tem.id=_cnt;
if((i+j)&1) _1.push_back(tem);
else _2.push_back(tem);
}
}
for(int i=0; i<_1.size(); i++)
{
add_edge(s,_1[i].id,_1[i].w);
add_edge(_1[i].id,s,0);
}

for(int i=0; i<_2.size(); i++)
{
add_edge(_2[i].id,t,_2[i].w);
add_edge(t,_2[i].id,0);
}

for(int i=0; i<_1.size(); i++)
{
if(_1[i].id%m!=0)
add_edge(_1[i].id,_1[i].id+1,inf),add_edge(_1[i].id+1,_1[i].id,0);
if(_1[i].id%m!=1)
add_edge(_1[i].id,_1[i].id-1,inf),add_edge(_1[i].id-1,_1[i].id,0);
if(_1[i].id+m<=n*m)
add_edge(_1[i].id,_1[i].id+m,inf),add_edge(_1[i].id+m,_1[i].id,0);
if(_1[i].id-m>=1)
add_edge(_1[i].id,_1[i].id-m,inf),add_edge(_1[i].id-m,_1[i].id,0);
}
printf("%d\n",sum-Dinic());
}
}
avatar Decaku 菜菜菜