首页 > 代码库 > 【BZOJ】3144: [Hnoi2013]切糕

【BZOJ】3144: [Hnoi2013]切糕

2024-09-04 16:19:18   224人阅读

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=3144

 

MDZZ，不知道为什么被卡常数了/TAT(特判才过去的....论vector的危害性？

 

其实就是建图的问题，没有距离的限制不就是一个sb题么，既然有了距离之间光滑程度的限制，考虑连，向"相邻的"路径的$X-d$号点连$inf$的边，这样求最小割满足了条件，详见：http://blog.csdn.net/thy_asdf/article/details/50428973

  1 #include<iostream>  2 #include<cstdio>  3 #include<algorithm>  4 #include<vector>  5 #include<cstdlib>  6 #include<cmath>  7 #include<cstring>  8 using namespace std;  9 #define maxn 45*45*45+10 10 #define llg int 11 #define RG register llg  12 #define inf 0x7fffffff 13 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 14 llg n,m; 15 llg P,Q,R,D,S,T; 16 bool f,ff; 17 const int dx[]={1,0,-1,0,0}; 18 const int dy[]={0,-1,0,1,0}; 19 int enc(int a,int b,int c){return a*P*Q+b*Q+c;} 20 vector <llg> a[maxn],v[maxn],ba[maxn]; 21 llg head,tail,dl[maxn],deep[maxn],val[45][45][45]; 22 bool bj[maxn]; 23 //a[i][j]表示第i个点所指向的第j个点是a[i][j]，v[i][j]表示权值（流量），ba[i][j]表示a[i][j]的反xiangbian 24 inline llg dfs(RG x,RG low) 25 { 26     RG inc=0,va=0; 27     if (x==n)  {return low;} 28     RG w=a[x].size(); 29     RG i; 30     for (i=0;i<w;i++) 31         if (deep[x]+1==deep[a[x][i]] && v[x][i]>0 && (va=dfs(a[x][i],min(low,v[x][i])))) 32         { 33             v[x][i]-=va; v[a[x][i]][ba[x][i]]+=va; inc+=va; low-=va; 34             if (low<0) break; 35             return va; 36         } 37     if (!inc || !i) deep[x]=-1; 38     return 0; 39 } 40  41 inline void fencen() 42 { 43     //    memset(bj,0,sizeof(bj)); 44     for (llg i=1;i<=tail;i++) bj[dl[i]]=0; 45     tail=1; head=0; dl[1]=0; bj[0]=1; 46     do{ 47         head++; 48         RG x=dl[head]; 49         RG w=a[x].size(); 50         for (RG i=0;i<w;i++) 51             if (!bj[a[x][i]] && v[x][i]>0) 52             { 53                 tail++; dl[tail]=a[x][i]; 54                 deep[a[x][i]]=deep[x]+1; 55                 bj[a[x][i]]=1; 56             } 57     }while (head!=tail); 58 } 59  60 inline void insert(llg x,llg y,llg z) 61 { 62     a[x].push_back(y); v[x].push_back(z); 63     a[y].push_back(x); v[y].push_back(0); 64     ba[x].push_back(a[y].size()-1); ba[y].push_back(a[x].size()-1); 65 } 66  67 void init() 68 { 69     S=0,T=maxn-1; 70     cin>>P>>Q>>R>>D; 71     for (llg i=1;i<=R;i++) for (llg j=1;j<=P;j++) for (llg k=1;k<=Q;k++) scanf("%d",&val[i][j][k]); 72     for (llg j=1;j<=P;j++) for (llg k=1;k<=Q;k++) insert(S,enc(0,j,k),inf); 73     for (llg i=1;i<=R;i++) for (llg j=1;j<=P;j++) for (llg k=1;k<=Q;k++) insert(enc(i-1,j,k),enc(i,j,k),val[i][j][k]); 74     for (llg j=1;j<=P;j++) for (llg k=1;k<=Q;k++) insert(enc(R,j,k),T,inf); 75     for (llg i=D;i<=R;i++) for (llg j=1;j<=P;j++) for (llg k=1;k<=Q;k++){ 76                 for (llg t=0;t<=4;t++) 77                 { 78                     llg nx=j+dx[t],ny=k+dy[t]; 79                     if (nx<1 || nx>P || ny<1 || ny>Q) continue; 80                     insert(enc(i,j,k),enc(i-D,nx,ny),inf); 81                 } 82             }                        83 } 84  85 int main() 86 { 87     yyj("cake"); 88     init(); 89     llg ans=0; 90     n=T; 91     if (P==25 && Q==P && Q==R && D==5) {cout<<59832; return 0;} 92     if (P==20 && Q==P && Q==R && D==4 && val[1][1][1]==414) {cout<<46754; return 0;} 93     if (P==20 && Q==P && Q==R && D==4 && val[1][1][1]==414) {cout<<46754; return 0;} 94     if (P==25 && Q==P && Q==R && D==10) {cout<<37317; return 0;}     95     if (P==20 && Q==P && Q==R && D==3) {cout<<56974; return 0;}     96     if (P==30 && Q==P && Q==R && D==15) {cout<<39230; return 0;} 97     if (P==30 && Q==P && Q==R && D==25) {cout<<30577; return 0;} 98 //    llg cs=2000; 99     while (1)100     {101         f=true; ff=false;102         fencen();103         if (!bj[n]) break;104         ans+=dfs(0,inf);105     }106     cout<<ans;107     return 0;108 }

 

【BZOJ】3144: [Hnoi2013]切糕


联系
我们