自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:46:57，当前版本为作者最后更新于2023-04-30 19:29:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

$n$ 倍经验题。

发现种植小麦还是向日葵其实就是让你把每个格子划分到两个集合之一中。于是发现与 happiness 这道题唯一的区别就是本题中 $c_{i,j}$ 表示的是分到不同集合的代价。那么做个简单的转化，把选择不同集合的代价变成先给答案减 $c_{i,j}$，然后计算选择相同集合的贡献。然后建图网络流即可。

具体一些，源点向每个点连容量为 $a_{i,j}$ 的边，每个点向汇点连容量为 $b_{i,j}$ 的边。对于同时选小麦有贡献的两个点（选向日葵的贡献同理），我们新建一个节点 $x$，源点向它连容量 $c_{i,j}$ 的边，再由它向这两个点连容量为 $\infty$ 的边。从最小割的角度考虑易证其正确性（要么割掉与源点的连边，要么割掉与汇点的连边，这保证了每个点不同时选小麦和向日葵），那么答案即为总量减最小割，结束。

代码

/*
  author: PEKKA_l  
 */
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define int long long
#define INF 1000000000000
#define dn(x,y) ((x-1)*m+y)

int n,m,a[75][75],b[75][75],c[75][75],d[75][75],ans,head[30005],cnt=1,cntd,s,t;

struct edge
{
	int son,val,next;
}edge[1000005];
void adde(int x,int y,int z) {edge[++cnt]={y,z,head[x]}; head[x]=cnt; edge[++cnt]={x,0,head[y]}; head[y]=cnt;}

int nowb[30005],dis[30005],maxflow;
queue <int> Q;

bool bfs()
{
	memset(dis,127,sizeof(dis)); dis[s]=0; Q.push(s);
	while(!Q.empty())
	{
		int nr=Q.front(); Q.pop();
		for(int i=head[nr];i>0;i=edge[i].next)
		{
			if(edge[i].val&&dis[nr]+1<dis[edge[i].son])
			{
				dis[edge[i].son]=dis[nr]+1; Q.push(edge[i].son);
			}
		}
	}
	return dis[t]<INF;
}
int dfs(int x,int nfl)
{
	if(x==t) return nfl;
	int nuse=0;
	for(int i=nowb[x];i>0;i=edge[i].next)
	{
		nowb[x]=i;
		if(edge[i].val&&dis[x]+1==dis[edge[i].son])
		{
			int flw=dfs(edge[i].son,min(nfl-nuse,edge[i].val));
			nuse+=flw; edge[i].val-=flw; edge[i^1].val+=flw;
			if(nuse==nfl) return nuse;
		}
	}
	return nuse;
}
void dinic()
{
	while(bfs())
	{
		memcpy(nowb,head,sizeof(head)); maxflow+=dfs(s,INF);
	}
}

signed main()
{
	cin>>n>>m; s=0,t=30000; cntd=n*m;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {cin>>a[i][j]; adde(s,dn(i,j),a[i][j]); ans+=a[i][j];}
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {cin>>b[i][j]; adde(dn(i,j),t,b[i][j]); ans+=b[i][j];}
	for(int i=1;i<=n;i++) for(int j=1;j<=m-1;j++) 
	{
		cin>>c[i][j]; ans+=c[i][j]; 
		cntd++; adde(s,cntd,c[i][j]); adde(cntd,dn(i,j),INF); adde(cntd,dn(i,j+1),INF);
		cntd++; adde(cntd,t,c[i][j]); adde(dn(i,j),cntd,INF); adde(dn(i,j+1),cntd,INF);
	}
	for(int i=1;i<=n-1;i++) for(int j=1;j<=m;j++) 
	{
		cin>>d[i][j]; ans+=d[i][j]; 
		cntd++; adde(s,cntd,d[i][j]); adde(cntd,dn(i,j),INF); adde(cntd,dn(i+1,j),INF);
		cntd++; adde(cntd,t,d[i][j]); adde(dn(i,j),cntd,INF); adde(dn(i+1,j),cntd,INF);
	}
	dinic(); ans-=maxflow; cout<<ans<<endl;
}

多倍经验可见 此题单 第一、六、七题。