The minimum cut of the problem of how to get the number of squares in Luogu P2774

Title Description

In a chessboard with m*n squares, there is a positive integer in each square. Now we need to take the number from the grid, so that any two numbers in the grid have no common edge, and the sum of the number taken out is the largest. This paper attempts to design a data retrieval algorithm that meets the requirements. For a given checkerboard, program to find the maximum sum according to the requirements of fetching.

I / O format

Input format:
The first row has two positive integers m and N, which respectively represent the number of rows and columns of the chessboard. The next M lines, each with n positive integers, represent the number in the checkerboard.

Output format:
At the end of program operation, the maximum sum of fetches will be output

Example of input and output

Input example ා 1:
3 3
1 2 3
3 2 3
2 3 1
Output example:
11
Explain

m,n<=100

Analysis: the maximum weight independent set of a bipartite graph. Obviously, black-and-white coloring (that is, a color is different from the surrounding color) satisfies the bipartite graph. Obviously if we choose a point, we can't choose the surrounding points. That is to say, the source point is connected with the edge of a white point weight, the white point is connected with the edge of inf, and the black point is connected with the edge of the black point weight. Obviously it's a minimum cut. So we can add up all the point weights and then subtract the minimum cut.

dalao said that he would not use the maximum weight independent set of a general graph, but the maximum independent set of a general graph can be made of a tree with flowers.

Code:

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>

const int maxn=105;
const int inf=0x3f3f3f3f;

using namespace std;

int n,m,i,j,ans,cnt,s,t;
int a[maxn][maxn],ls[maxn*maxn],dis[maxn*maxn];

struct node{
    int y,next,op,c;
}g[maxn*maxn*8];

queue <int> q;

void add(int x,int y,int w)
{
    g[++cnt].y=y; g[cnt].c=w; g[cnt].op=cnt+1; g[cnt].next=ls[x]; ls[x]=cnt; 
    g[++cnt].y=x; g[cnt].c=0; g[cnt].op=cnt-1; g[cnt].next=ls[y]; ls[y]=cnt;
}

int fc(int x,int y)
{
    return (x-1)*m+y;
}

bool bfs()
{
    for (int i=s;i<=t;i++) dis[i]=0;
    dis[s]=1;
    while (!q.empty()) q.pop();
    q.push(s);
    while (!q.empty())
    {
        int u=q.front();
        q.pop();
        for (int i=ls[u];i>0;i=g[i].next)
        {
            int v=g[i].y;
            if ((dis[v]==0) && (g[i].c))
            {
                dis[v]=dis[u]+1;
                if (v==t) return true;
                q.push(v);
            }
        }
    }
    return false;
}

int dfs(int x,int maxf)
{
    if ((x==t) || (maxf==0)) return maxf;
    int ret=0;
    for (int i=ls[x];i>0;i=g[i].next)
    {
        int y=g[i].y;
        if ((dis[x]+1==dis[y]) && (g[i].c))
        {
            int f=dfs(y,min(g[i].c,maxf-ret));
            g[i].c-=f;
            g[g[i].op].c+=f;
            ret+=f;
        }
    }
    return ret;
}

void dinic()
{
    while (bfs()) ans-=dfs(s,inf);
}
int main()
{
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
            ans+=a[i][j];
        }
    }   
    s=0; t=n*m+1;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            if ((i+j)%2)
            {
                add(s,fc(i,j),a[i][j]);
                if (i>1) add(fc(i,j),fc(i-1,j),inf);
                if (i<n) add(fc(i,j),fc(i+1,j),inf);
                if (j>1) add(fc(i,j),fc(i,j-1),inf);
                if (j<m) add(fc(i,j),fc(i,j+1),inf);
            }
            else add(fc(i,j),t,a[i][j]);
        }
    }   
    dinic();
    printf("%d",ans);
}

Posted on Wed, 01 Apr 2020 21:09:04 -0700 by czambran