首页 > 代码库 > 【BZOJ】3144: [Hnoi2013]切糕
【BZOJ】3144: [Hnoi2013]切糕
题目链接: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]切糕
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。