bzoj千题计划142：bzoj3144: [Hnoi2013]切糕-白红宇

bzoj千题计划142：bzoj3144: [Hnoi2013]切糕

阅读量：4967 次

发布时间：2019-06-12

本文共 4476 字，大约阅读时间需要 14 分钟。

如果D=2 ，两个点，高度为4，建图如下

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std; #define N 64005#define M 323205const int inf=2e9; int n;int P,Q,R,D;int cost[41][41][41]; int tot=1;int front[N],nxt[M<<1],to[M<<1],val[M<<1],from[M<<1];int lev[N],num[N];int path[N];int cur[N]; int src,decc;int dx[4]={-1,0,1,0};int dy[4]={
   0,1,0,-1};void read(int &x){    x=0; char c=getchar();    while(!isdigit(c))  c=getchar();     while(isdigit(c)) { x=x*10+c-'0'; c=getchar();  }}void add(int u,int v,int w){    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; from[tot]=u; val[tot]=w;    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; from[tot]=v; val[tot]=0;   // cout<
          <<' '<
           
            <<' '<
            
             <<'\n';}bool bfs(){ queue
             
              q; for(int i=src;i<=decc;++i) lev[i]=decc; q.push(decc); lev[decc]=0; int now,t; while(!q.empty()) { now=q.front(); q.pop(); for(int i=front[now];i;i=nxt[i]) { t=to[i]; if(lev[t]==decc && val[i^1]) { lev[t]=lev[now]+1; q.push(t); } } } return lev[src]!=decc;} int augment(){ int now=decc,flow=inf; int i; while(now!=src) { i=path[now]; flow=min(flow,val[i]); now=from[i]; } now=decc; while(now!=src) { i=path[now]; val[i]-=flow; val[i^1]+=flow; now=from[i]; } return flow;} int isap(){ int flow=0; if(!bfs()) return 0; memset(num,0,sizeof(num)); for(int i=src;i<=decc;++i) num[lev[i]]++,cur[i]=front[i]; int now=src,t; while(lev[src]<=decc) { if(now==decc) { flow+=augment(); now=src; } bool advanced=false; for(int i=cur[now];i;i=nxt[i]) { t=to[i]; if(lev[t]==lev[now]-1 && val[i]) { advanced=true; path[t]=i; cur[now]=i; now=t; break; } } if(!advanced) { int mi=decc; for(int i=front[now];i;i=nxt[i]) if(val[i]) mi=min(mi,lev[to[i]]); if(!--num[lev[now]]) break; num[lev[now]=mi+1]++; cur[now]=front[now]; if(now!=src) now=from[path[now]]; } } return flow;}int turn(int i,int j,int k){ return ((i-1)*Q+j-1)*(R+1)+k;}void build(){ int nx,ny; for(int i=1;i<=P;++i) for(int j=1;j<=Q;++j) for(int k=1;k<=R;++k) { add(turn(i,j,k),turn(i,j,k+1),cost[i][j][k]); if(k>D) { for(int d=0;d<4;++d) { nx=i+dx[d]; ny=j+dy[d]; if(nx>=1 && nx<=P && ny>=1 && ny<=Q) add(turn(i,j,k),turn(nx,ny,k-D),inf); } } } decc=P*Q*(R+1)+1; for(int i=1;i<=P;++i) for(int j=1;j<=Q;++j) { add(src,turn(i,j,1),inf); add(turn(i,j,R+1),decc,inf); }}int main(){ freopen("nutcake.in","r",stdin); freopen("nutcake.out","w",stdout); read(P); read(Q); read(R); read(D); for(int i=1;i<=R;++i) for(int j=1;j<=P;++j) for(int k=1;k<=Q;++k) { read(cost[j][k][i]); // cout<
              
               <<' '<
               
                <<' '<
                <<' '<
                 
                  <<'\n'; } build(); cout<

2018.3.20 考试代码

#include
       
        #include
        
         #include
         
          using namespace std;const int inf=2e9;#define M 400000#define N 70000int P,Q,R,D;int a[41][41][41];int front[N],nxt[M<<1],to[M<<1],cap[M<<1],tot=1;int src,decc;int lev[N],cur[N];queue
          
           q;void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void init(){    read(P); read(Q); read(R);    read(D);    for(int i=1;i<=R;++i)        for(int j=1;j<=P;++j)            for(int k=1;k<=Q;++k)                read(a[i][j][k]);}int turn(int i,int j,int k){    return ((i-1)*Q+j-1)*(R+1)+k;}void add(int u,int v,int val){    to[++tot]=v; nxt[tot]=front[u]; front[u]=tot; cap[tot]=val;    to[++tot]=u; nxt[tot]=front[v]; front[v]=tot; cap[tot]=0;}void build(){    decc=(R+1)*P*Q+1;    for(int i=1;i<=P;++i)        for(int j=1;j<=Q;++j)        {            add(src,turn(i,j,1),inf);            for(int k=1;k<=R;++k)                add(turn(i,j,k),turn(i,j,k+1),a[k][i][j]);            add(turn(i,j,R+1),decc,inf);        }    for(int i=1;i<=P;++i)        for(int j=1;j<=Q;++j)            for(int k=D+2;k<=R+1;++k)            {                if(i>1) add(turn(i,j,k),turn(i-1,j,k-D),inf);                if(i
           
            1) add(turn(i,j,k),turn(i,j-1,k-D),inf);                if(j