本文主要是介绍Codeforces Gym 101128F (UVA Live 7277) Landscaping 最小割，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目传送门
给你一个地图，每一块分为高低两种，从高到低、低到高需要花a元，把一块从高改到低或者从低改到高需要b元。
问从上到下，从左到右遍历最少花多少钱。
对每条红线，要么跨越花a元，要么改造一块地花b元。
两种地形构成二分图。
源点连低地，汇点连高地，流量为b，表示改造地需要b元。
地图上相邻点之间连接，流量为a，表示跨越红线需要a元。由于不知道改造后哪些是高、哪些是低，所有相邻的点无论地形全部需要连接。
最后的答案就是最小割。
官方题解
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <bitset>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn=2505,maxk=100005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
int head[maxn],dist[maxn],current[maxn];
char s[55][55];
int num;struct Edge {int from,to,flow,pre;
};
Edge edge[maxk];void addedge(int from,int to,int flow) {edge[num]=(Edge){from,to,flow,head[from]};head[from]=num++;edge[num]=(Edge){to,from,0,head[to]};head[to]=num++;
}bool bfs (int n) {queue<int> q;q.push(0);memset(dist,-1,sizeof(dist));dist[0]=0;while (!q.empty()) {int now=q.front();q.pop();for (int i=head[now];i!=-1;i=edge[i].pre) {int to=edge[i].to;if (dist[to]==-1&&edge[i].flow>0) {dist[to]=dist[now]+1;q.push(to);}}}return dist[n]!=-1;
}int dfs(int now,int flow,int n) {int f;if (now==n) return flow;for (int i=current[now];i!=-1;i=edge[i].pre) {int to=edge[i].to;current[now]=i;if (dist[now]+1==dist[to]&&edge[i].flow>0&&(f=dfs(to,min(flow,edge[i].flow),n))) {edge[i].flow-=f;edge[i^1].flow+=f;return f;}}return 0;
}int dinic(int n) {int sum=0,f;while (bfs(n)) {memcpy(current,head,sizeof(head));while (f=dfs(0,inf,n)) sum+=f;}return sum;
}int main() {memset(head,-1,sizeof(head));num=0;int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};int n,m,a,b,i,j,k;scanf("%d%d%d%d",&n,&m,&a,&b);for (i=1;i<=n;i++) {scanf("%s",s[i]+1);for (j=1;j<=m;j++) {if (s[i][j]=='.') addedge(0,(i-1)*n+j,b);else addedge((i-1)*n+j,n*m+1,b);}}for (i=1;i<=n;i++) {for (j=1;j<=m;j++) {for (k=0;k<4;k++) {int x=i+dir[k][0],y=j+dir[k][1];if (x>0&&x<=n&&y>0&&y<=m) {addedge((i-1)*n+j,(x-1)*n+y,a);}}}}int ans=dinic(m*n+1);printf("%d\n",ans);return 0;
}
这篇关于Codeforces Gym 101128F (UVA Live 7277) Landscaping 最小割的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
