BZOJ 3144 HNOI 2013 切糕 最小割

BZOJ 3144 HNOI 2013 切糕 最小割

題目大意：給出一個三維的點陣，沒個點都有可能被切割，代價就是這個點的權值。相鄰的切割點的高度差不能超過D，問最小的花費使得上下分開。

思路：很裸的最小割模型，很神的建圖。

S->第一層的點，f:INF

所有點->它下面的點，f:INF

一個點的入->一個點的出，f:val[i]

(i,j,k) - > (i - d,j,k)，f:INF

最下面一層的點->T:f:INF

然後跑最小割就是答案。

為什麼見：http://www.cnblogs.com/zyfzyf/p/4182168.html OTZ ZYF

CODE:

#include 
#include 
#include 
#include 
#include 
#define MAX 130000
#define MAXE 1200000
#define S 0
#define T (MAX - 1)
#define INF 0x3f3f3f3f
using namespace std;
const int dx[] = {0,1,-1,0,0};
const int dy[] = {0,0,0,1,-1};

struct MaxFlow{
	int head[MAX],total;
	int next[MAXE],aim[MAXE],flow[MAXE];
	int deep[MAX];
	
	MaxFlow() {
		total = 1;
		memset(head,0,sizeof(head));
	}
	void Add(int x,int y,int f) {
		next[++total] = head[x];
		aim[total] = y;
		flow[total] = f;
		head[x] = total;
	}
	void Insert(int x,int y,int f) {
		Add(x,y,f);
		Add(y,x,0);
	}
	bool BFS() {
		static queue q;
		while(!q.empty())	q.pop();
		memset(deep,0,sizeof(deep));
		deep[S] = 1;
		q.push(S);
		while(!q.empty()) {
			int x = q.front(); q.pop();
			for(int i = head[x]; i; i = next[i])
				if(flow[i] && !deep[aim[i]]) {
					deep[aim[i]] = deep[x] + 1;
					q.push(aim[i]);
					if(aim[i] == T)	return true;
				}
		}
		return false;
	}
	int Dinic(int x,int f) {
		if(x == T)	return f;
		int temp = f;
		for(int i = head[x]; i; i = next[i]) 
			if(flow[i] && temp && deep[aim[i]] == deep[x] + 1) {
				int away = Dinic(aim[i],min(flow[i],temp));
				if(!away)	deep[aim[i]] = 0;
				flow[i] -= away;
				flow[i^1] += away;
				temp -= away;
			}
		return f - temp;
	}
}solver;

int P,Q,R,D;
int src[50][50][50],num[50][50][50],cnt;

int main()
{
	cin >> P >> Q >> R >> D;
	for(int i = 1; i <= R; ++i)
		for(int j = 1; j <= P; ++j)
			for(int k = 1; k <= Q; ++k) {
				scanf("%d",&src[i][j][k]),num[i][j][k] = ++cnt;
				solver.Insert(num[i][j][k] << 1,num[i][j][k] << 1|1,src[i][j][k]);
			}
	for(int i = 1; i <= P; ++i)
		for(int j = 1; j <= Q; ++j) {
			solver.Insert(S,num[1][i][j] << 1,INF);
			solver.Insert(num[R][i][j] << 1|1,T,INF);
		}
	for(int i = 1; i <= R; ++i)
		for(int j = 1; j <= P; ++j)
			for(int k = 1; k <= Q; ++k) {
				if(i != R)
					solver.Insert(num[i][j][k] << 1|1,num[i + 1][j][k] << 1,INF);
				for(int d = 1; d <= 4; ++d) {
					int fx = j + dx[d],fy = k + dy[d];
					if(!fx || !fy || fx > P || fy > Q)	continue;
					if(i - D > 0)	solver.Insert(num[i][j][k] << 1,num[i - D][fx][fy] << 1,INF);
				}
			}
	int max_flow = 0;
	while(solver.BFS())
		max_flow += solver.Dinic(S,INF);
	cout << max_flow << endl;
	return 0;
}