[bzoj3144]切糕

超、凢脫俗 2021-11-17 15:36 210阅读 0赞

对于P\*Q的矩形中每一个点挂一条长度为R的链，流量分别是下一个点的点权（链尾是inf），然后对于每一个点连向四周的后D个点连一条inf的边。

考虑最小割，当割掉某一条链的一条边，就表示选择该边，那么如果割掉的两条边相差大于D，那么一定可以顺着在前面的那个点走到另一条路上在走到汇点，不是满足条件的割。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 #define N 100005
     4 #define id ((i-1)*n+j-1)*m+k
     5 #define inf 0x3f3f3f3f
     6 struct ji{
     7     int nex,to,len;
     8 }edge[N*8];
     9 queue<int>q;
    10 int E,n,m,t,l,p,head[N],work[N],d[N];
    11 void add(int x,int y,int z){
    12     edge[E].nex=head[x];
    13     edge[E].to=y;
    14     edge[E].len=z;
    15     head[x]=E++;
    16     if (E&1)add(y,x,0);
    17 }
    18 bool bfs(){
    19     memset(d,-1,sizeof(d));
    20     q.push(0);
    21     d[0]=0;
    22     while (!q.empty()){
    23         int k=q.front();
    24         q.pop();
    25         for(int i=head[k];i!=-1;i=edge[i].nex)
    26             if ((edge[i].len)&&(d[edge[i].to]<0)){
    27                 d[edge[i].to]=d[k]+1;
    28                 q.push(edge[i].to);
    29             }
    30     }
    31     return d[n]>=0;
    32 }
    33 int dfs(int k,int s){
    34     if (k==n)return s;
    35     int p;
    36     for(int &i=work[k];i!=-1;i=edge[i].nex)
    37         if ((edge[i].len)&&(d[edge[i].to]==d[k]+1)){
    38             p=dfs(edge[i].to,min(s,edge[i].len));
    39             if (p){
    40                 edge[i].len-=p;
    41                 edge[i^1].len+=p;
    42                 return p;
    43             }
    44         }
    45     return 0;
    46 }
    47 int dinic(){
    48     int k,ans=0;
    49     while (bfs()){
    50         memcpy(work,head,sizeof(head));
    51         while (k=dfs(0,inf))ans+=k;
    52     }
    53     return ans;
    54 }
    55 int main(){
    56     scanf("%d%d%d%d",&n,&m,&t,&l);
    57     memset(head,-1,sizeof(head));
    58     for(int i=1;i<=t;i++)
    59         for(int j=1;j<=n;j++)
    60             for(int k=1;k<=m;k++){
    61                 scanf("%d",&p);
    62                 if (i==1)add(0,id,p);
    63                 else add(id-n*m,id,p);
    64                 if (i==t)add(id,n*m*t+1,inf);
    65                 if (i>l){
    66                     if (k>1)add(id,id-l*n*m-1,inf);
    67                     if (k<m)add(id,id-l*n*m+1,inf);
    68                     if (j>1)add(id,id-l*n*m-m,inf);
    69                     if (j<n)add(id,id-l*n*m+m,inf);
    70                 }
    71             }
    72     n=n*m*t+1;
    73     printf("%d",dinic());
    74 }

转载于:https://www.cnblogs.com/PYWBKTDA/p/11249763.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211116/5e22846453ce49f88783713f18f697ea.png