P9276 题解
honglan0301
·
·
题解
题目分析
发现种植小麦还是向日葵其实就是让你把每个格子划分到两个集合之一中。于是发现与 [happiness](https://www.luogu.com.cn/problem/P1646) 这道题唯一的区别就是本题中 $c_{i,j}$ 表示的是分到不同集合的代价。那么做个简单的转化，把选择不同集合的代价变成先给答案减 $c_{i,j}$，然后计算选择相同集合的贡献。然后建图网络流即可。
具体一些，源点向每个点连容量为 $a_{i,j}$ 的边，每个点向汇点连容量为 $b_{i,j}$ 的边。对于同时选小麦有贡献的两个点（选向日葵的贡献同理），我们新建一个节点 $x$，源点向它连容量 $c_{i,j}$ 的边，再由它向这两个点连容量为 $\infty$ 的边。从最小割的角度考虑易证其正确性（要么割掉与源点的连边，要么割掉与汇点的连边，这保证了每个点不同时选小麦和向日葵），那么答案即为总量减最小割，结束。
## 代码
```cpp
/*
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;
}
```
多倍经验可见 [此题单](https://www.luogu.com.cn/training/1230) 第一、六、七题。