并不对劲的方格取数问题

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例

输出样例

说明

m,n<=100

***********************怕不是要dp********************

这道题如果不是在网络流24题中，我可能真把它当dp了。

用最大流最小割定理求出至少需要不取多少数才能把剩下的数分开。

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#define ll long long
#define maxk 110
#define maxm 200010
#define maxn 20010
using namespace std;
ll n,m,a[maxk][maxk],sum;
ll v[maxm],fir[maxn],fl[maxm],nxt[maxm],cnt;
ll ss,tt,dis[maxn],vis[maxn],maxflow,inf[5];
ll read()
{
    ll x=0,f=1;
    char ch=getchar();
    while(isdigit(ch)==0&&ch!='-')ch=getchar();
    if(ch=='-')ch=getchar(),f=-1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    return x*f;
}
void addedge(ll u1,ll v1,ll fl1)
{
    v[cnt]=v1,fl[cnt]=fl1,nxt[cnt]=fir[u1],fir[u1]=cnt++;
    v[cnt]=u1,fl[cnt]=0,nxt[cnt]=fir[v1],fir[v1]=cnt++;
}
ll bfs()
{
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    queue<ll>q;
    vis[ss]=1;
    dis[ss]=0;
    q.push(ss);
    while(!q.empty())
    {
        ll u=q.front();q.pop();
        for(ll k=fir[u];k!=-1;k=nxt[k])
        {
            ll vv=v[k];
            if(fl[k]>0)
            {
                if(dis[vv]>dis[u]+1 || dis[vv]==-1)
                {
                    dis[vv]=dis[u]+1;
                    if(!vis[vv])q.push(vv);
                    vis[vv]=1;
                }
            }
        }
        vis[u]=0;
    }
    return dis[tt]==-1?0:1;
}
ll dfs(ll u,ll nowflow)
{
    ll tmp,sum=0;
    if(u==tt || nowflow==0)return nowflow;
    for(ll k=fir[u];k!=-1;k=nxt[k])
    {
        if(nowflow<=0)break;
        ll vv=v[k];
        if(fl[k]>0 && dis[u]+1==dis[vv] 
        && (tmp=dfs(vv,min(nowflow,fl[k])))>0)
        {
            nowflow-=tmp;
            sum+=tmp;
            fl[k]-=tmp;
            fl[k^1]+=tmp;
        }
    }
    return sum;
}
void add(ll x,ll y)
{
    ll z=x*m+y;
    if((x+y)&1)
    {
        addedge(ss,z,inf[0]);
        addedge(z,z+n*m,a[x][y]);
        if(x>0)addedge(z+n*m,(x-1)*m+y,inf[0]);
        if(x<n-1)addedge(z+n*m,(x+1)*m+y,inf[0]);
        if(y>1)addedge(z+n*m,x*m+y-1,inf[0]);
        if(y<m)addedge(z+n*m,x*m+y+1,inf[0]);
    }
    else
    {
        addedge(z,z+n*m,a[x][y]);
        addedge(z+n*m,tt,inf[0]);
    }
}
int main() 
{
    memset(inf,0x7f,sizeof(inf));
    memset(fir,-1,sizeof(fir));
    n=read(),m=read();ss=0,tt=n*m+n*m+1;
    for(ll i=0;i<n;i++)
    {
        for(ll j=1;j<=m;j++)
        {
            a[i][j]=read();
            sum+=a[i][j];
            add(i,j);
        }
    }
    /*for(ll i=0;i<=tt;i++)
    {
        cout<<i<<":";
        for(ll k=fir[i];k!=-1;k=nxt[k])
        {
            cout<<v[k]<<" "<<fl[k]<<endl;
        }
    }*/
    while(bfs())
    {
        maxflow+=dfs(ss,inf[0]);
    }
    cout<<sum-maxflow;
    return 0;
}

View Code

听说网络流可以解决绝大部分问题（就是时间复杂度……），你信吗？