题目

传送门

思路

我也不知道为什么隔壁的大佬以上来就说是网络流

之后我就成功被带偏了

对于此题，我们发现如果直接求答案显然是不现实的

但是我们可以求出不符合答案的方案

用总的方案来减去不合法的方案就行了

对于两个点可以这样来建图

其中u，v是虚点

而且通过分流讨论很容易就可以说明这个图的正确性

同时，虽然点的数量和边的数量很多

但是这个图建出来就是一个天然的分成图

所以果断选择dinic

代码

#include<iostream>
#include<cstring>
#include<climits>
#include<queue>
using namespace std;
int n,m;
int tot;
int s,e;
int dx[3]={0,1,0};
int dy[3]={0,0,1};
int w[5][105][105];
long long ans;
struct network_edge_dinic
{
    #define maxn 1800000
    int s,t;
    int cnt;
    int cur[maxn];
    int head[maxn];
    int to[maxn<<1];
    long long val[maxn<<1];
    int nxt[maxn<<1];
    int d[maxn];
    #undef maxn
    void init()
    {
        cnt=1;
    }
    void add_edge(int u,int v,int w)
    {
        to[++cnt]=v;
        val[cnt]=w;
        nxt[cnt]=head[u];
        head[u]=cnt;
        to[++cnt]=u;
        val[cnt]=0;
        nxt[cnt]=head[v];
        head[v]=cnt;
    }
    long long dfs(int u,long long f)
    {
        if(u==t)
            return f;
        long long minn=0,summ=0;
        for(int& i=cur[u];i;i=nxt[i])
        {
            int v=to[i];
            if(d[v]==d[u]+1&&val[i]>0)
            {
                minn=dfs(v,min(f,val[i]));
                f-=minn;
                val[i]-=minn;
                val[i^1]+=minn;
                summ+=minn;
                if(!f)
                    break;
            }  
        }
        if(!summ)
            d[u]=-1;
        return summ;
    }
    bool bfs()
    {
        memset(d,-1,sizeof(d));
        queue<int> q;
        q.push(s);
        d[s]=0;
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            for(int i=head[u];i;i=nxt[i])
            {
                int v=to[i];
                if(d[v]==-1&&val[i]>0)
                {
                    d[v]=d[u]+1;
                    q.push(v);
                }
            }
        }
        if(d[t]!=-1)
            return 1;
        return 0;
    }
    long long dinic(int S,int T)
    {
        s=S;
        t=T;
        int ans=0;
        while(bfs())
        {
            for(int i=1;i<=tot;i++)
                cur[i]=head[i];
            ans+=dfs(s,1e9);
        }
        return ans;
    }
}g;
int gethash(int x,int y)
{
    return (x-1)*m+y;
}
bool inside(int a,int b)
{
    if(1<=a&&a<=n&&1<=b&&b<=m)
        return 1;
    return 0;
}
int main()
{
    g.init();
    cin>>n>>m;
    s=n*m+1;
    e=n*m+2;
    tot=n*m+2;
    for(int i=1;i<=n;i++)
    {  
        for(int j=1;j<=m;j++)
        {
            int x;
            cin>>x;
            ans+=x;
            g.add_edge(s,gethash(i,j),x);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            cin>>x;
            ans+=x;
            g.add_edge(gethash(i,j),e,x);
        }
    }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            int x;
            cin>>x;
            ans+=x;
            g.add_edge(s,++tot,x);
            g.add_edge(tot,gethash(i,j),INT_MAX);
            g.add_edge(tot,gethash(i+1,j),INT_MAX);
        }
    for(int i=1;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            int x;
            cin>>x;
            ans+=x;
            g.add_edge(++tot,e,x);
            g.add_edge(gethash(i,j),tot,INT_MAX);
            g.add_edge(gethash(i+1,j),tot,INT_MAX);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
        {
            int x;
            cin>>x;
            ans+=x;
            g.add_edge(s,++tot,x);
            g.add_edge(tot,gethash(i,j),INT_MAX);
            g.add_edge(tot,gethash(i,j+1),INT_MAX);
        }

    for(int i=1;i<=n;i++)
        for(int j=1;j<m;j++)
        {
            int x;
            cin>>x;
            ans+=x;
            g.add_edge(++tot,e,x);
            g.add_edge(gethash(i,j),tot,INT_MAX);
            g.add_edge(gethash(i,j+1),tot,INT_MAX);
        }
    cout<<ans-g.dinic(s,e);
    return 0;
}

习题：happiness（网络流）