流为A. 这样我们只有当高地和低地同时存在的时候

时间:2022-05-05 02:18:00

标题问题大意:给你一个N*M的矩阵,此中“#”代表高地,“.”代表低地,我们有N+M辆车,从高地转到低地需要花费A,我们使得高地酿成低地或者是使得低地酿成高地的花费为B.我们的车每列从上到下,每行从左到右行驶,问最小花费是几多。

其实我看不懂别人的解法,我也不会,先放这里。

思路:
很显然我们不能直接Dp,因为我们当前的块如果变革了,会对之前很多功效进行了影响,我们考虑多加维度打消这个后效性无果,不妨事考虑网络流。
我们要求最小花费,不难想到最小割,那么考虑建图。
①首先我们可以将点分成两类,这样我们使得低地分成一类,剩下的分成一类,那么就组成了二分图。
我们将源点连入各个低所在,流为B,我们再将各个高所在连入汇点,流也为B.
②然后我们将各个相邻的点,都要连上,,流为A.
这样我们只有当高地和低地同时存在的时候,才会有所花费(有流从源点到汇点。)。
建好图之后跑最大流即可。

#include<stdio.h> #include<string.h> #include<queue> using namespace std; struct node { int from; int to; int w; int next; }e[100*65*4]; char a[55][55]; int cur[8500]; int head[8500]; int divv[8500]; int fx[4]={1,0,-1,0}; int fy[4]={0,1,0,-1}; int n,m,A,B; int cont,ss,tt; void add(int from,int to,int w) { e[cont].from=from; e[cont].w=w; e[cont].to=to; e[cont].next=head[from]; head[from]=cont++; } int num(int x,int y) { return 1+m*x+y; } void Get_map() { cont=0; memset(head,-1,sizeof(head)); ss=n*m+1;tt=ss+1; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(a[i][j]=='.') { add(ss,num(i,j),B); add(num(i,j),ss,0); } else { add(num(i,j),tt,B); add(tt,num(i,j),0); } for(int k=0;k<4;k++) { int xx=fx[k]+i; int yy=fy[k]+j; if(xx>=0&&xx<n&&yy>=0&&yy<m) { add(num(i,j),num(xx,yy),A); add(num(xx,yy),num(i,j),0); } } } } } int makedivv() { memset(divv,0,sizeof(divv)); divv[ss]=1; queue<int >s; s.push(ss); while(!s.empty()) { int u=s.front(); if(u==tt)return 1; s.pop(); for(int i=head[u];i!=-1;i=e[i].next) { int w=e[i].w; int v=e[i].to; if(divv[v]==0&&w) { divv[v]=divv[u]+1; s.push(v); } } } return 0; } int Dfs(int u,int maxflow,int tt) { if(u==tt)return maxflow; int ret=0; for(int &i=cur[u];i!=-1;i=e[i].next) { int v=e[i].to; int w=e[i].w; if(divv[v]==divv[u]+1&&w) { int f=Dfs(v,min(maxflow-ret,w),tt); e[i].w-=f; e[i^1].w+=f; ret+=f; if(ret==maxflow)return ret; } } return ret; } void Dinic() { int ans=0; while(makedivv()==1) { memcpy(cur,head,sizeof(head)); ans+=Dfs(ss,0x3f3f3f3f,tt); } printf("%d\n",ans); } int main() { while(~scanf("%d%d%d%d",&n,&m,&A,&B)) { for(int i=0;i<n;i++)scanf("%s",a[i]); Get_map(); Dinic(); } }

GYM 101128 F.Landscaping【最小割--还不懂】

标签:

原文地点:https://www.cnblogs.com/tennant/p/8971068.html