BZOJ 1475(方格取数-递归sap完全+二分图最大点独立集MAXWVIS)

1475: 方格取数

Time Limit: 5 Sec   Memory Limit: 64 MB

Submit: 409  

Solved: 215

[​​Submit​​][​​Status​​][​​Discuss​​]

Description

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

Input

第一行一个数n；（n<=30） 接下来n行每行n个数描述一个方阵

Output

仅一个数，即最大和

Sample Input

2
1 2
3 5

Sample Output

6

就本题我做了我的第一个最大点独立集（二分图）

推荐《最小割模型在信息学竞赛中的应用》

首先转化模型

我们把原图黑白染色，以黑点，白点为U,V建立二分图

则本题转化为求最大点独立集T，任意边2端不能全取

先求最小点覆盖集T‘，任意边2端至少取1端

于是把T’取反得到T（见证明）

建图时注意：

1.建图时建的是有向图（你只能从白向黑引线，用最小割求解，否则E容量都为∞，最小割只能沿着S或T的一排割），故反向边容量必须为0

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXn (30+10)
#define MAXN (1000+10)
#define INF (1000000000)
#define MAXM (100000)
#define For(i,n) for(int i=1;i<=n;i++)
#define Forp(p,x) for(int p=pre[x];p;p=next[p])
int s,t,a[MAXn][MAXn],n;
int pre[MAXN]={0},edge[MAXM],next[MAXM]={0},weight[MAXM],size=1;
void addedge(int u,int v,int w)
{
  edge[++size]=v;
  weight[size]=w;
  next[size]=pre[u];
  pre[u]=size;
}
void addedge2(int u,int v,int w){if (w) addedge(u,v,w),addedge(v,u,0);}
int d[MAXN]={0},cnt[MAXN];
int sap(int x,int flow)
{
  if (x==t) return flow;
  int nowflow=0;
  Forp(p,x)
  {
    int &v=edge[p];  
    if (d[v]==d[x]-1&&weight[p])
    {
      int fl=sap(v,min(weight[p],flow));
      weight[p]-=fl,weight[p^1]+=fl,flow-=fl,nowflow+=fl;
      if (!flow) return nowflow;
    }
  }
  if (!(--cnt[d[x]++])) d[s]=t+1;
  cnt[d[x]]++;
  return nowflow;
}
int main()
{
  scanf("%d",&n);
  int tot=0;
  For(i,n) For(j,n) cin>>a[i][j],tot+=a[i][j];
  s=n*n+1;t=s+1;
  For(i,n) For(j,n)
  {
    if ((i+j)%2)
    {
      if (i^n) addedge2(n*(i-1)+j,n*i+j,INF);
      if (j^n) addedge2(n*(i-1)+j,n*(i-1)+j+1,INF);
    }
    else
    {
      if (i^n) addedge2(n*i+j,n*(i-1)+j,INF);
      if (j^n) addedge2(n*(i-1)+j+1,n*(i-1)+j,INF);
    }    
  }
  For(i,n) For(j,n) if ((i+j)%2) addedge2(s,n*(i-1)+j,a[i][j]);else addedge2(n*(i-1)+j,t,a[i][j]);
  int ans=0;
  cnt[0]=t;
  while (d[s]<=t) ans+=sap(s,INF);
  printf("%d\n",tot-ans); 
  return 0;
}