BZOJ3144[Hnoi2013]切糕——最小割

阳光穿透心脏的1/2处 2022-01-05 15:09 206阅读 0赞

## 题目描述 ##

![1_286_29.jpg][]

## 输入 ##

第一行是三个正整数P,Q,R，表示切糕的长P、 宽Q、高R。第二行有一个非负整数D，表示光滑性要求。接下来是R个P行Q列的矩阵，第z个 矩阵的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R)。   
100%的数据满足P,Q,R≤40，0≤D≤R，且给出的所有的不和谐值不超过1000。

## 输出 ##

仅包含一个整数，表示在合法基础上最小的总不和谐值。

## 样例输入 ##

2 2 2  
1  
6 1  
6 1  
2 6  
2 6

## 样例输出 ##

## 提示 ##

最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1

根据题意显然我们需要在二维平面的每个坐标上删除一个点。删除点不好办，我们将点转化成边：将第三维坐标为$z$的点变成连接第$z$层与第$z+1$层的边，即连接$(x,y,z)$与$(x,y,z+1)$，流量为$v(x,y,z)$，然后源点连向第一层的点，最后一层的点连向汇点。如果不考虑$D$的限制，直接按上述连边跑最小割即可。但现在考虑$D$的限制，我们将$(x,y,z)$连向$(x',y',z-D)$，流量为$INF$表示这条边不能被割。可以发现如果相邻两个坐标割的边第三维坐标差大于$D$时，就可以有流量绕过被割的边从相邻坐标的边流过去。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<bitset>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define INF 1000000000
    using namespace std;
    int head[70000];
    int next[800000];
    int to[800000];
    int val[800000];
    int d[70000];
    int q[70000];
    int n,m,r,D;
    int f[50][50][50];
    int tot=1;
    int ans;
    int S,T;
    int dx[7]={0,1,0,-1};
    int dy[7]={1,0,-1,0};
    void add(int x,int y,int v)
    {
    	tot++;
    	next[tot]=head[x];
    	head[x]=tot;
    	to[tot]=y;
    	val[tot]=v;
    	tot++;
    	next[tot]=head[y];
    	head[y]=tot;
    	to[tot]=x;
    	val[tot]=0;
    }
    bool bfs(int S,int T)
    {
    	int r=0;
    	int l=0;
    	memset(q,0,sizeof(q));
    	memset(d,-1,sizeof(d));
    	q[r++]=S;
    	d[S]=0;
    	while(l<r)
    	{  
    		int now=q[l];
    		for(int i=head[now];i;i=next[i])
    		{
    			if(d[to[i]]==-1&&val[i]!=0)
    			{
    				d[to[i]]=d[now]+1;
    				q[r++]=to[i];
    			}
    		}
    		l++;
    	}
    	return d[T]!=-1;
    }
    int dfs(int x,int flow)
    {
    	if(x==T)
    	{
    		return flow;
    	}
    	int now_flow;
    	int used=0;
    	for(int i=head[x];i;i=next[i])
    	{
    		if(d[to[i]]==d[x]+1&&val[i]!=0)
    		{
    			now_flow=dfs(to[i],min(flow-used,val[i]));
    			val[i]-=now_flow;
    			val[i^1]+=now_flow;
    			used+=now_flow;
    			if(now_flow==flow)
    			{
    				return flow;
    			}
    		}
    	}
    	if(used==0)
    	{
    		d[x]=-1;
    	}
    	return used;
    }
    void dinic()
    {
    	while(bfs(S,T)==true)
    	{
    		ans+=dfs(S,0x3f3f3f);
    	}
    }
    int calc(int x,int y,int z)
    {
    	return y+(x-1)*m+(z-1)*n*m;
    }
    int main()
    {
    	scanf("%d%d%d%d",&n,&m,&r,&D);
    	S=n*m*(r+1)+1;
    	T=S+1;
    	for(int k=1;k<=r;k++)
    	{
    		for(int i=1;i<=n;i++)
    		{
    			for(int j=1;j<=m;j++)
    			{
    				scanf("%d",&f[i][j][k]);
    			}
    		}
    	}
    	for(int i=1;i<=n;i++)
    	{
    		for(int j=1;j<=m;j++)
    		{
    			add(S,calc(i,j,1),INF);
    			for(int k=1;k<=r;k++)
    			{
    				add(calc(i,j,k),calc(i,j,k+1),f[i][j][k]);
    				if(k<=D)
    				{
    					continue;
    				}
    				for(int s=0;s<4;s++)
    				{
    					int fx=dx[s]+i,fy=dy[s]+j;
    					if(fx>=1&&fx<=n&&fy>=1&&fy<=m)
    					{
    						add(calc(i,j,k),calc(fx,fy,k-D),INF);
    					}
    				}
    			}
    			add(calc(i,j,r+1),T,INF);
    		}
    	}
    	dinic();
    	printf("%d",ans);
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10574345.html

[1_286_29.jpg]: https://www.lydsy.com/JudgeOnline/upload/201304/1%286%29.jpg