点覆盖集：无向图G的一个点集，使得该图中所有边都至少有一个端点在该集合内；
最小点权覆盖集：在带点权无向图G中，点权之和最小的覆盖集；
点独立集：无向图G的一个点集，使得任两个在该集合中的点在原图中都不相邻；
最大点权独立集：在带权无向图G中，点权之和最大的独立集；

解法：

对图中所有点进行0|1染色

0色：S向其连权值为该点权值的边，向相邻点连权值为inf的边

1色：向T连权值为该点权值的边

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 55*55, inf = 0x3f3f3f3f;
const int MAXM = MAXN*10;
int n, m;
struct _edge
{
    int v, nxt;
    int w;
    _edge(int vv, int ww, int nnxt):v(vv),w(ww),nxt(nnxt){}
    _edge(){}
}ee[MAXM];
int head[MAXN], cnt;
int cur[MAXN], dis[MAXN], gap[MAXN], pre[MAXN];
void add(int u, int v, int w)
{
    ee[cnt] = _edge(v,w,head[u]); head[u] = cnt++;
    ee[cnt] = _edge(u,0,head[v]); head[v] = cnt++;
}
int sap(int start,int end,int nodenum)
{
    memset(dis,0,4*MAXN);
    memset(gap,0,4*MAXN);
    memcpy(cur,head,4*MAXN);
    int u=pre[start]=start;
    int maxflow=0,aug=-1;
    gap[0]=nodenum;
    while(dis[start]<nodenum)
    {
        loop:
        for(int &i=cur[u];i!=-1;i=ee[i].nxt)
        {
            int v=ee[i].v;
            if(ee[i].w&&dis[u]==dis[v]+1)
            {
                if(aug==-1||aug>ee[i].w)
                    aug=ee[i].w;
                pre[v]=u;
                u=v;
                if(v==end)
                {
                    maxflow+=aug;
                    for(u=pre[u];v!=start;v=u,u=pre[u])
                    {
                        ee[cur[u]].w-=aug;
                        ee[cur[u]^1].w+=aug;
                    }
                    aug=-1;
                }
                goto loop;
            }
        }
        int mindis=nodenum;
        for(int i=head[u];i!=-1;i=ee[i].nxt)
        {
            int v=ee[i].v;
            if(ee[i].w && mindis>dis[v])
            {
                cur[u]=i;
                mindis=dis[v];
            }
        }
        if((--gap[dis[u]])==0)break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return maxflow;
}
void init()
{
    cnt = 0;
    memset(head, -1, sizeof head);
}
int main()   
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while (scanf("%d%d", &n, &m) != EOF)
    {
        int S = n*m, T = S+1, a, res = 0;
        init();
        for (int i = 0; i< n; ++i)
        {
            for (int j = 0; j< m; ++j)
            {
                scanf("%d", &a);
                res += a;
                int p = i*m+j;
                if ((i+j) & 1)
                    add(p, T, a);
                else
                {
                    add(S, p, a);
                    if (j > 0) add(p, p-1, inf);
                    if (j+1 < m) add(p, p+1, inf);
                    if (i > 0) add(p, p-m, inf);
                    if (i+1 < n) add(p, p+m, inf);
                }
            }
        }
        printf("%d\n", res - sap(S, T, T+1));
    }
    return 0;
}

推荐这篇博客的解法： http://blog.csdn.net/t1019256391/article/details/38036355

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 55*55, inf = 0x3f3f3f3f;
const int MAXM = MAXN*10;
int n, m;
char mmp[55][55];
struct _edge
{
    int v, nxt;
    int w;
    _edge(int vv, int ww, int nnxt):v(vv),w(ww),nxt(nnxt){}
    _edge(){}
}ee[MAXM];
int head[MAXN], cnt;
int cur[MAXN], dis[MAXN], gap[MAXN], pre[MAXN];
void add(int u, int v, int w)
{
    ee[cnt] = _edge(v,w,head[u]); head[u] = cnt++;
    ee[cnt] = _edge(u,0,head[v]); head[v] = cnt++;
}
int sap(int start,int end,int nodenum)
{
    memset(dis,0,4*MAXN);
    memset(gap,0,4*MAXN);
    memcpy(cur,head,4*MAXN);
    int u=pre[start]=start;
    int maxflow=0,aug=-1;
    gap[0]=nodenum;
    while(dis[start]<nodenum)
    {
        loop:
        for(int &i=cur[u];i!=-1;i=ee[i].nxt)
        {
            int v=ee[i].v;
            if(ee[i].w&&dis[u]==dis[v]+1)
            {
                if(aug==-1||aug>ee[i].w)
                    aug=ee[i].w;
                pre[v]=u;
                u=v;
                if(v==end)
                {
                    maxflow+=aug;
                    for(u=pre[u];v!=start;v=u,u=pre[u])
                    {
                        ee[cur[u]].w-=aug;
                        ee[cur[u]^1].w+=aug;
                    }
                    aug=-1;
                }
                goto loop;
            }
        }
        int mindis=nodenum;
        for(int i=head[u];i!=-1;i=ee[i].nxt)
        {
            int v=ee[i].v;
            if(ee[i].w && mindis>dis[v])
            {
                cur[u]=i;
                mindis=dis[v];
            }
        }
        if((--gap[dis[u]])==0)break;
        gap[dis[u]=mindis+1]++;
        u=pre[u];
    }
    return maxflow;
}
void init()
{
    cnt = 0;
    memset(head, -1, sizeof head);
}
int main()   
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
	int t, S, T, cs = 0, p;
	scanf("%d", &t);
    while (t--)
    {
    	
    	scanf("%d%d", &n, &m);
    	init();
    	S = (n+2)*(m+2); T = S+1;
    	for (int i = 1; i<= n; ++i)
    		scanf("%s", mmp[i]+1);
		for (int i = 0; i<= n+1; ++i)		
		for (int j = 0; j<= m+1; ++j)
		{
			if (i == 0 || j == 0 || i==n+1 || j == m+1)
   				mmp[i][j] = 'D';
			p = i*(m+2)+j;
			if ((i+j) & 1)
			{
				if (mmp[i][j] == 'D') 
					add(p, T, inf);
				if (mmp[i][j] == '.') 
					add(S, p, inf);
			}
			else
			{
				if (mmp[i][j] == '.') 
					add(p, T, inf);
				if (mmp[i][j] == 'D') 
					add(S, p, inf);				
			}
			
			if (i-1 >= 0) add(p, p-m-2, 1);
			if (i+1 < n+2) add(p, p+m+2, 1);
			if (j-1 >= 0) add(p, p-1, 1);
			if (j+1 < m+2) add(p, p+1, 1);
		}
		printf("Case %d: %d\n", ++cs, (n+1)*(m+2)+(n+2)*(m+1) - sap(S, T, T+1));
    }
    return 0;
}