首页 > 代码库 > bzoj 3144: [Hnoi2013]切糕 最小割
bzoj 3144: [Hnoi2013]切糕 最小割
3144: [Hnoi2013]切糕
Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 681 Solved: 375
[Submit][Status]
Description
.jpg)
Input
第一行是三个正整数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。
Output
仅包含一个整数，表示在合法基础上最小的总不和谐值。
Sample Input
2 2 2
1
6 1
6 1
2 6
2 6
1
6 1
6 1
2 6
2 6
Sample Output
6
HINT
最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1
一类经典的方案选择型最小割，感觉，非常神奇，不过这个是稠密图把我以前的dinic直接卡TLE了，发现一定要判断maxf==0时直接退出。
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;#define MAXN 50#define MAXH 50#define MAXE MAXV*10#define MAXV MAXN*MAXN*MAXH#define INF 0x3f3f3f3fconst int mov[4][2]={{0,1},{1,0},{-1,0},{0,-1}};struct Edge{ int np,val; Edge *next,*neg;}E[MAXE],*V[MAXV];int sour,sink=1;int tope=-1;void addedge(int x,int y,int z){// printf("Add:%d %d %d\n",x,y,z); E[++tope].np=y; E[tope].val=z; E[tope].next=V[x]; V[x]=&E[tope]; E[++tope].np=x; E[tope].val=0; E[tope].next=V[y]; V[y]=&E[tope]; V[x]->neg=V[y]; V[y]->neg=V[x];}int q[MAXV];int vis[MAXV],bfstime=0;int lev[MAXV];int bfs(){ int head=-1,tail=0; Edge *ne; int now; q[0]=sour; vis[sour]=++bfstime; while (head<tail) { now=q[++head]; for (ne=V[now];ne;ne=ne->next) { if (!ne->val || vis[ne->np]==bfstime)continue; vis[ne->np]=bfstime; q[++tail]=ne->np; lev[ne->np]=lev[now]+1; } } return vis[sink]==bfstime;}int dfs(int now,int maxf){ int t,ret=0; if (now==sink)return maxf; Edge *ne; for (ne=V[now];maxf && ne;ne=ne->next) { if (!ne->val || lev[ne->np]!=lev[now]+1)continue; t=dfs(ne->np,min(maxf,ne->val)); ne->val-=t; ne->neg->val+=t; maxf-=t; ret+=t; } if (maxf)lev[now]=-1; return ret;}int dinic(){ int ret=0; while (bfs()) { ret+=dfs(sour,INF); } return ret;}int n,m,h;int gid(int x,int y,int z){ return 2+x*m+y+z*m*n;}int a[MAXN][MAXN][MAXH];int main(){ freopen("input.txt","r",stdin); int i,j,k,k2,x,y,z; scanf("%d%d%d",&n,&m,&h); int d; scanf("%d",&d); for (k=1;k<=h;k++) for (i=1;i<=n;i++) for (j=1;j<=m;j++) { scanf("%d",&a[i][j][k]); addedge(gid(i,j,k-1),gid(i,j,k),a[i][j][k]); } for (i=1;i<=n;i++) for (j=1;j<=m;j++) for (k=1;k+d<=h;k++) for (k2=0;k2<4;k2++) if (i+mov[k2][0]>0 && i+mov[k2][0]<=n && j+mov[k2][1]>0 && j+mov[k2][1]<=m) { // addedge(gid(i,j,k),gid(i+mov[k2][0],j+mov[k2][1],k+d),INF); addedge(gid(i,j,k+d),gid(i+mov[k2][0],j+mov[k2][1],k),INF); } for (i=1;i<=n;i++) for (j=1;j<=m;j++) { addedge(sour,gid(i,j,0),INF); addedge(gid(i,j,h),sink,INF); } printf("%d\n",dinic());}
bzoj 3144: [Hnoi2013]切糕 最小割
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。