题目链接:https://cn.vjudge.net/contest/281959#problem/D
解题思路:二元组建图后跑最大流(等于最小割)
参考题解:http://www.cnblogs.com/chenyushuo/p/5146626.html?tdsourcetag=s_pctim_aiomsg
代码
#include <iostream> #include <bits/stdc++.h> using namespace std; const int inf=2147483647; struct node { int next,to,dis; }edge[600030]; int head[100010],cur[100010],deep[100010]; int n,m,cnt=2,maxflow; int nextt[4][2]={{0,1},{1,0},{-1,0},{0,-1}}; void addedge(int from,int to,int dis) { edge[cnt].to=to; edge[cnt].dis=dis; edge[cnt].next=head[from]; head[from]=cnt++; edge[cnt].to=from; edge[cnt].dis=0; edge[cnt].next=head[to]; head[to]=cnt++; } bool bfs(int s,int t) { memset(deep,0,sizeof(deep)); queue<int>q; while(!q.empty()) q.pop(); memcpy(cur,head,sizeof(head)); deep[s]=1; q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); for(int i=head[now];i!=-1;i=edge[i].next) { if(!deep[edge[i].to]&&edge[i].dis) { deep[edge[i].to]=deep[now]+1; q.push(edge[i].to); } } } return deep[t]; } int dfs(int now,int t,int limit) { if(!limit||now==t) return limit; int flow=0; for(int i=cur[now];i!=-1;i=edge[i].next) { // cur[now]=i; // if(deep[edge[i].to]==deep[now]+1&&( // f=dfs(edge[i].to,t,min(limit,edge[i].dis)))) // { // flow+=f; // limit-=f; // edge[i].dis-=f; // edge[i^1].dis+=f; // if(!limit)break; // } if(edge[i].dis&&deep[edge[i].to]==deep[now]+1) { int d=dfs(edge[i].to,t,min(limit,edge[i].dis)); flow+=d; limit-=d; edge[i].dis-=d; edge[i^1].dis+=d; } } if(!flow)deep[now]=0; return flow; } void dinic(int s,int t) { while(bfs(s,t)) maxflow+=dfs(s,t,inf); } int hashh[111][111],tot=0; int main() { ios::sync_with_stdio(false); memset(head,-1,sizeof(head)); int summ=0; cin>>n>>m; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { hashh[i][j]=++tot; } } cnt=0; int s,t; s=0; t=tot*3+1; int d; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>d; summ+=d; addedge(s,hashh[i][j],d); } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>d; summ+=d; addedge(hashh[i][j],t,d); } } int now=tot; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>d; summ+=d; now++; addedge(now,hashh[i][j],inf); for(int k=0;k<4;k++) { int tx=i+nextt[k][0],ty=j+nextt[k][1]; if(!tx||tx>n||!ty||ty>m)continue; addedge(now,hashh[tx][ty],inf); } addedge(s,now,d); } } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>d; now++; summ+=d; addedge(hashh[i][j],now,inf); for(int k=0;k<4;k++) { int tx=i+nextt[k][0],ty=j+nextt[k][1]; if(!tx||tx>n||!ty||ty>m)continue; addedge(hashh[tx][ty],now,inf); } addedge(now,t,d); } } maxflow=0; dinic(s,t); cout<<summ-maxflow<<endl; return 0; }
来jh博客复制答案