[JSOI2015]圈地

原题链接：P6094 [JSOI2015]圈地

题意简述

把一块 \(n \times m\) 的地分给两个人，选择分出第 \(i\) 行第 \(j\) 列的地可以获得 \(a_{i,j}\) 的收益。
要在两个人分到的地中间建墙，使得两个人分到的地完全隔离，建两个格子之间的墙需要花费一定代价。
最大化总收益与总代价的差
\(1 \le n, m \le 200\)
细节还是见原题吧QAQ

思路与解答

你看它数据范围这么小肯定是个图论建模，而且大概率网络流
你看这题相当于要把地分成两块，并且代价最小。
那就是一个最小割嘛
然后考虑怎么建图
你在建图时需要保证能选或不选一块地，并且要能够“割”开两块属于不同的人的地
假设两个人分别为 A 和 B，那么首先把相邻两块地之间连边，流量为建墙的花费，表示如果要“割”开这两块地就要砍掉这条边，当然要不要砍再说；注意这里无法保证你要怎么“割”，所以两块地要分别向对方连边。
那么之后建一个超级源点 \(S\)，把 \(S\) 和所有 A 想要的地连边，流量为这块地的收益，如果在权衡之后不选，就把这条边“割”掉；同理，把所有 B 想要的地和超级汇点 \(T\) 连边，流量也为这块地的收益。
那么你在这张图中跑一遍最小割，得到的结果就是你需要付出的最小代价，这里是包括了选或者不选一块地。
所以你只需要把总收益，即所有结点的收益和减去最小割即可。
最后，你只需要知道最小割等于最大流，就可以愉快的切题了

Code

#include <cstdio>

#include <queue>

#include <iostream>

#include <cstring>

#define abs(x) (x<0?-x:x)

using namespace std;

const int MAXN = 80010;

const int INF = 0x3f3f3f3f; 

int n, m;

inline int id(int i, int j){return (i-1)*m+j;}

struct edge{

	int ne, to, fl;

	edge(int N=0,int T=0,int F=0):ne(N),to(T),fl(F){}

}e[MAXN*6];

int fir[MAXN], num = 1;

int s, t;

inline void adde(int a, int b, int c)

{

	e[++num] = edge(fir[a], b, c);

	fir[a] = num;

}

inline void join(int a, int b, int c)

{

	adde(a, b, c);

	adde(b, a, 0);

}

int dep[MAXN], cur[MAXN];

queue<int> q;

bool bfs(int s, int t)

{

	for(int i=0;i<=n*m+1;i++)

		dep[i] = 0, cur[i] = fir[i];

	while(!q.empty()) q.pop();

	q.push(s);

	dep[s] = 1;

	while(!q.empty())

	{

		int u = q.front();

		q.pop();

		for(int i=fir[u];i;i=e[i].ne)

		{

			int v = e[i].to;

			if(dep[v] || !e[i].fl) continue;

			dep[v] = dep[u] + 1;

			q.push(v);

		}

	}

	return dep[t];

}

int dfs(int u, int fln)

{

	if(u == t) return fln;

	int res = 0;

	for(int& i=cur[u];i;i=e[i].ne)

	{

		int v = e[i].to;

		if(!e[i].fl || dep[v] != dep[u]+1) continue;

		int sum = dfs(v, min(fln, e[i].fl));

		e[i].fl -= sum;

		e[i^1].fl += sum;

		fln -= sum;

		res += sum;

		if(!fln) break;

	}

	if(!res) dep[u] = 0;

	return res;

}

inline int dinic()

{

	int res = 0;

	while(bfs(s, t)) res += dfs(s, INF);

	return res;

}

int main()

{

	scanf("%d%d",&n,&m);

	s = 0; t = n*m+1;

	int sum = 0;

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<=m;j++)

		{

			int a;

			scanf("%d",&a);

			if(a > 0) join(s, id(i, j), a);

			if(a < 0) join(id(i, j), t, -a);

			sum += abs(a);

		}

	}

	for(int i=1;i<n;i++)

	{

		for(int j=1;j<=m;j++)

		{

			int a;

			scanf("%d",&a);

			join(id(i, j), id(i+1, j), a);

			join(id(i+1, j), id(i, j), a);

		}

	}

	for(int i=1;i<=n;i++)

	{

		for(int j=1;j<m;j++)

		{

			int a;

			scanf("%d",&a);

			join(id(i, j), id(i, j+1), a);

			join(id(i, j+1), id(i, j), a);

		}

	}

	printf("%d\n",sum-dinic());

	return 0;

}

巴特西

[JSOI2015]圈地

题意简述

思路与解答

Code

最新文章

热门文章