最大流最大点权独立集

方格取数(2)

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4185 Accepted Submission(s): 1300

Problem Description

给你一个m*n的格子的棋盘，每个格子里面有一个非负数。
从中取出若干个数，使得任意的两个数所在的格子没有公共边，就是说所取数所在的2个格子不能相邻，并且取出的数的和最大。

Input

包括多个测试实例，每个测试实例包括2整数m,n和m*n个非负数(m<=50,n<=50)

Output

对于每个测试实例，输出可能取得的最大的和

Sample Input

Sample Output

分析：

分析：黑白染色，s到每个白色格子一条边，容量是格子的值，黑格子到t一条边，容量是格子的值，相邻格子之间inf的边。
（1）点覆盖集：无向图G的一个点集，使得该图中所有边都至少有一个端点在该集合内。
（2）最小点权覆盖集：在带点权无向图G中，点权之和最小的覆盖集。
（3）点独立集：无向图G的一个点集，使得任两个在该集合中的点在原图中都不相邻。
（4）最大点权独立集：在带权无向图G中，点权之和最大的独立集。
定理：
1. 最小点权覆盖集=最小割=最大流
2. 最大点权独立集=总权-最小点权覆盖集

程序：

#include"stdio.h"
#include"string.h"
#define M 100005
#define inf 999999999
int min(int a,int b)
{
    return a<b?a:b;
}
struct st
{
    int u,v,w,next;
}edge[M];
int head[M],work[M],q[M],dis[M],t;
void init()
{
    t=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v,int w)
{
    edge[t].u=u;
    edge[t].v=v;
    edge[t].w=w;
    edge[t].next=head[u];
    head[u]=t++;
    edge[t].u=v;
    edge[t].v=u;
    edge[t].w=0;
    edge[t].next=head[v];
    head[v]=t++;
}
int bfs(int S,int T)
{
    int rear=0;
    memset(dis,-1,sizeof(dis));
    q[rear++]=S;
    dis[S]=0;
    for(int i=0;i<rear;i++)
    {
        for(int j=head[q[i]];j!=-1;j=edge[j].next)
        {
            int v=edge[j].v;
            if(edge[j].w&&dis[v]==-1)
            {
                dis[v]=dis[q[i]]+1;
                q[rear++]=v;
                if(v==T)
                    return 1;
            }
        }
    }
    return 0;
}
int dfs(int cur,int a,int T)
{
    if(cur==T)
        return a;
    for(int &i=work[cur];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(edge[i].w&&dis[v]==dis[cur]+1)
        {
            int tt=dfs(v,min(a,edge[i].w),T);
            if(tt)
            {
                edge[i].w-=tt;
                edge[i^1].w+=tt;
                return tt;
            }
        }
    }
    return 0;
}
int Dinic(int S,int T)
{
    int ans=0;
    while(bfs(S,T))
    {
        memcpy(work,head,sizeof(head));
        while(int tt=dfs(S,inf,T))
            ans+=tt;
    }
    return ans;
}
int main()
{
    int n,i,j,m;
    int a[55][55];
    while(scanf("%d%d",&n,&m)!=-1)
    {
        init();
        int sum=0;
        for(i=0;i<n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&a[i][j]);
                sum+=a[i][j];
            }
        }
        for(i=0;i<n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if((i+j)&1)
                {
                    if(i+1<n)
                    add(i*m+j,(i+1)*m+j,inf);
                    if(j+1<=m)
                    add(i*m+j,i*m+j+1,inf);
                    if(i-1>=0)
                    add(i*m+j,(i-1)*m+j,inf);
                    if(j-1>=1)
                    add(i*m+j,i*m+j-1,inf);
                    add(0,i*m+j,a[i][j]);
                }

                else
                    add(i*m+j,n*m+1,a[i][j]);
            }
        }
        int ans=Dinic(0,n*m+1);
        printf("%d
",sum-ans);
    }
}