题目链接：https://cn.vjudge.net/problem/HDU-1565
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取的数所在的2个格子不能相邻，并且取出的数的和最大。
看了一下题目，立刻就想起来曾经好像在网络流专题里做过类似题目，
一翻博客，果然找到了这题的brother：http://www.cnblogs.com/dilthey/p/7401563.html
题解：
解法①：
既然，连这题的加强版 HDU 1569 - 方格取数 都可以用网络流做，这题当然也可以，代码几乎就是一点点修改：
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#define MAX 405
#define INF 0x3f3f3f3f
#define id(i,j) (i-1)*n+j
using namespace std;
struct Edge{
int u,v,c,f;
};
struct Dinic
{
int s,t;
vector<Edge> E;
vector<int> G[MAX];
bool vis[MAX];
int lev[MAX];
int cur[MAX];
void init(int l,int r)
{
E.clear();
for(int i=l;i<=r;i++) G[i].clear();
}
void addedge(int from,int to,int cap)
{
E.push_back((Edge){from,to,cap,});
E.push_back((Edge){to,from,,});
int m=E.size();
G[from].push_back(m-);
G[to].push_back(m-);
}
bool bfs()
{
memset(vis,,sizeof(vis));
queue<int> q;
q.push(s);
lev[s]=;
vis[s]=;
while(!q.empty())
{
int now=q.front(); q.pop();
for(int i=,_size=G[now].size();i<_size;i++)
{
Edge edge=E[G[now][i]];
int nex=edge.v;
if(!vis[nex] && edge.c>edge.f)
{
lev[nex]=lev[now]+;
q.push(nex);
vis[nex]=;
}
}
}
return vis[t];
}
int dfs(int now,int aug)
{
if(now==t || aug==) return aug;
int flow=,f;
for(int& i=cur[now],_size=G[now].size();i<_size;i++)
{
Edge& edge=E[G[now][i]];
int nex=edge.v;
if(lev[now]+ == lev[nex] && (f=dfs(nex,min(aug,edge.c-edge.f)))>)
{
edge.f+=f;
E[G[now][i]^].f-=f;
flow+=f;
aug-=f;
if(!aug) break;
}
}
return flow;
}
int maxflow()
{
int flow=;
while(bfs())
{
memset(cur,,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}
}dinic;
int n,grid[][],sum;
int d[][]={{,+},{+,},{,-},{-,}};
bool inmap(int i,int j){return( <=i && i<=n && <=j && j<=n );}
int main()
{
while(scanf("%d",&n)!=EOF)
{
dinic.init(,n*n+);
dinic.s=, dinic.t=n*n+;
sum=;
for(int i=;i<=n;i++)
{
for(int j=;j<=n;j++)
{
scanf("%d",&grid[i][j]);
sum+=grid[i][j];
if((i+j)%)
{
for(int k=;k<;k++) if(inmap(i+d[k][],j+d[k][])) dinic.addedge(id(i,j), id(i+d[k][],j+d[k][]), INF);
dinic.addedge(dinic.s, id(i,j), grid[i][j]);
}
else dinic.addedge(id(i,j), dinic.t, grid[i][j]);
}
}
printf("%d\n",sum-dinic.maxflow());
}
}
解法②：
当然，既然放在状压DP专题，当然也说明了这种题目，在列数在比较小的情况下，可以用状压DP做（HDU1569因为列数达到50，所以不行）；
首先，由于1<<20的状态数，还是偏大了点，依然选择类似于http://www.cnblogs.com/dilthey/p/7604432.html中筛选状态的操作，得到最多的状态数为17711；
然后，设dp[r][i]：表示第r行为状态i时（显然这个i在二进制表示下，每一位上，0表示不取对应位置的数，1表示取），从第一行到第r行能取到的最大的和；
而要得到dp[r][i]，只需要把dp[r-1][j]枚举一遍，做相应的一定的计算，再保证维护dp[r][i]始终为最大即可，这就是状态转移；
其中所谓“做相应的一定的计算”，需要一个calc(r, state)函数：
calc(r, state)返回值为：第r行当状态为state时，取到的数之和；
AC代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,grid[][],ans;
int dp[][];
int state[],state_cnt;
int calc(int r,int state)
{
int ans=;
int cnt=n;
while(state)
{
if(state&) ans+=grid[r][cnt];
state=state>>;
cnt--;
}
return ans;
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;i++) for(int j=;j<=n;j++) scanf("%d",&grid[i][j]);
state_cnt=;
for(int i=;i<(<<n);i++)
{
if(i&(i<<)) continue;
dp[][state_cnt]=calc(,i);
state[state_cnt++]=i;
}
for(int r=;r<=n;r++)
{
for(int i=;i<state_cnt;i++)//枚举第r行状态
{
for(int j=;j<state_cnt;j++)//枚举第r-1行状态
{
if(state[i]&state[j]) continue;
dp[r][i]=max(dp[r][i],dp[r-][j]+calc(r,state[i]));
}
}
} ans=;
for(int i=;i<state_cnt;i++) ans=max(ans,dp[n][i]);
printf("%d\n",ans);
}
}
PS.本题其实和POJ 1185：http://www.cnblogs.com/dilthey/p/7604432.html比较像，做法思路一脉相承，会做POJ1185的话，做这题应该不难。