网络流24题之九方格取数问题

内容

填坑

地址：luogu2774

题目描述

在一个有 m*n 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 2 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

输入输出格式

输入格式：

第 1 行有 2 个正整数 m 和 n，分别表示棋盘的行数和列数。接下来的 m 行，每行有 n 个正整数，表示棋盘方格中的数。

输出格式：

程序运行结束时，将取数的最大总和输出

输入输出样例

输入样例#1：

输出样例#1：

方哥

模型

二分图点权最大独立集，转化为最小割模型，从而用最大流解决。

实现

首先把棋盘黑白染色，使相邻格子颜色不同，所有黑色格子看做二分图X集合中顶点，白色格子看做Y集合顶点，建立附加源S汇T。

1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。
2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。
3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。

求出网络最大流，要求的结果就是所有格子中数值之和减去最大流量。

分析

这是一个二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 = 所有点权 – 最小点权覆盖集 = 所有点权 – 最小割集 = 所有点权 – 网络最大流。

对于一个网络，除去冗余点（不存在一条ST路径经过的点），每个顶点都在一个从S到T的路径上。割的性质就是不存在从S到T的路径，简单割可以认为割边关联的非ST节点为割点，而在二分图网络流模型中每个点必关联到一个割点（否则一定还有增广路，当前割不成立），所以一个割集对应了一个覆盖集（支配集）。最小点权覆盖集就是最小简单割，求最小简单割的建模方法就是把XY集合之间的变容量设为无穷大，此时的最小割就是最小简单割了。

代码：

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
#define M 10000
#define N 1000
#define min(x,y) ((x<y)?(x):(y))
using namespace std;
struct node
{
    int from,to,next,flow;
}e[M];
int tot=-1,st[M],dis[N];
int n,m,x,y,z;
void add(int x,int y,int z)
{
    e[++tot].to=y;
    e[tot].from=x;
    e[tot].flow=z;
    e[tot].next=st[x];
    st[x]=tot;
}
void add_edge(int x,int y,int z)
{add(x,y,z),add(y,x,0);}
int bfs(int s,int t)
{
    int now;
    queue<int>que;
    memset(dis,-1,sizeof dis);
    dis[s]=1;
    que.push(s);
    while (!que.empty())
    {
        int now=que.front();
        que.pop();
        for (int i=st[now];~i;i=e[i].next)
            if (dis[e[i].to]<0&&e[i].flow>0)
                dis[e[i].to]=dis[now]+1,
                que.push(e[i].to);
    }
    if (dis[t]>0) return 1;
    return 0;
}
int finds(int x,int y,int low)
{
    int ans;
    if (x==y)
        return low;
    for (int i=st[x];~i;i=e[i].next)
        if (e[i].flow>0 && dis[x]+1==dis[e[i].to] && (ans=finds(e[i].to,y,min(low,e[i].flow))))
        {
            e[i].flow-=ans;
            e[i^1].flow+=ans;
            return ans;
        }
    return 0;
}
int Dinic(int s,int t)
{
    int flow=0;
    while(bfs(s,t))
    {
        while(x=finds(s,t,0x3f3f3f3f))
            flow+=x;
    }
    return flow;
}
//memset(e,-1,sizeof e);
//memset(st,-1,sizeof st);
int map[N][N];
main()
{
    scanf("%d%d",&m,&n);
    int S=0,T=n*m+1,t=0,sum=0;
    int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}};
    memset(e,-1,sizeof e);
    memset(st,-1,sizeof st);
    int i,j,k,c;
    for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
        {
            scanf("%d",&x);
            sum+=x;
            map[i][j]=++t;
            if ((i+j)%2==0)
                add_edge(S,t,x);
            else
                add_edge(t,T,x);
        }
    for (i=1;i<=m;i++)
        for (j=1;j<=n;j++)
            if ((i+j)%2==0)
                for (k=0;k<4;k++)
                {
                    int x=i+dir[k][0],y=j+dir[k][1];
                    if (x>=1 && x<=m && y>=1 && y<=n)
                        add_edge(map[i][j],map[x][y],0x3f3f3f3f);
                }

    printf("%d\n",sum-Dinic(S,T));

}

网络流24题之九 方格取数问题

题目描述

输入输出格式

输入输出样例

网络流24题之九方格取数问题