洛谷 P2774 方格取數問題

題目背景

none!

題目描述

在一個有 m*n 個方格的棋盤中，每個方格中有一個正整數。現要從方格中取數，使任意 2 個數所在方格沒有公共邊，且取出的數的總和最大。試設計一個滿足要求的取數算法。對于給定的方格棋盤，按照取數要求程式設計找出總和最大的數。

輸入輸出格式

輸入格式：

第 1 行有 2 個正整數 m 和 n，分别表示棋盤的行數和列數。接下來的 m 行，每行有 n 個正整數，表示棋盤方格中的數。

輸出格式：

程式運作結束時，将取數的最大總和輸出

輸入輸出樣例

輸入樣例#1：

3 3
1 2 3
3 2 3
2 3 1       

輸出樣例#1：

11      

說明

解題思路

　　一道和

騎士共存問題

差不多的題目，二分圖黑白染色後跑最大獨立集，這裡每個白格向四周連邊，而不是馬能攻擊到的地方(廢話)。

源代碼

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>


int n,m;
int a[1000][1000]={0};
int S=0;
inline int id(int x,int y)
{
    return (x-1)*m+y;
}

int s,t;
struct Edge{
    int next,to,flow;
}e[1000010];
int cnt=2,head[1000]={0};
void add(int u,int v,int f)
{
    e[cnt]={head[u],v,f};
    head[u]=cnt++;
    e[cnt]={head[v],u,0};
    head[v]=cnt++;
}


int dis[1000]={0};
bool bfs()
{
    memset(dis,0,sizeof(dis));
    std::queue<int> q;
    q.push(s);
    dis[s]=1;
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].next)
        {
            int v=e[i].to;
            if(dis[v]||!e[i].flow) continue;
            dis[v]=dis[u]+1;
            q.push(v);
        }
    }
    return dis[t]!=0;
}

int dfs(int u,int f)
{
    if(u==t||f==0) return f;
    int flow_sum=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].to;
        if(dis[v]!=dis[u]+1||!e[i].flow) continue;
        int temp=dfs(v,std::min(e[i].flow,f-flow_sum));
        e[i].flow-=temp;
        e[i^1].flow+=temp;
        flow_sum+=temp;
        if(flow_sum>=f) break;
    }
    if(!flow_sum) dis[u]=-1;
    return flow_sum;
}

int dinic()
{
    int ans=0;
    while(bfs())
    {
        while(int temp=dfs(s,0x7fffffff))
            ans+=temp;
    }
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);
    s=n*m+1,t=s+1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&a[i][j]),S+=a[i][j];
    int bh[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if((i+j)&1)
            {
                add(s,id(i,j),a[i][j]);
                for(int k=0;k<4;k++)
                {
                    int x=i+bh[k][0],y=j+bh[k][1];
                    if(x>=1&&x<=n&&y>=1&&y<=m)
                        add(id(i,j),id(x,y),0x7fffffff);
                }
            }
            else
                add(id(i,j),t,a[i][j]);
        }
    }
    printf("%d\n",S-dinic());
    return 0;
}