bzoj 3144: [Hnoi2013]切糕最小割

2022-07-10 07:45:49

3144: [Hnoi2013]切糕

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 681 Solved: 375
[Submit][Status]

Description

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

Sample Output

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 0x3f3f3f3f

const int mov[][]={{,},{,},{-,},{,-}};

struct Edge

{

        int np,val;

        Edge *next,*neg;

}E[MAXE],*V[MAXV];

int sour,sink=;

int tope=-;

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=;

        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=;

int lev[MAXV];

int bfs()

{

        int head=-,tail=;

        Edge *ne;

        int now;

        q[]=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]+;

                }

        }

        return vis[sink]==bfstime;

}

int dfs(int now,int maxf)

{

        int t,ret=;

        if (now==sink)return maxf;

        Edge *ne;

        for (ne=V[now];maxf && ne;ne=ne->next)

        {

                if (!ne->val || lev[ne->np]!=lev[now]+)continue;

                t=dfs(ne->np,min(maxf,ne->val));

                ne->val-=t;

                ne->neg->val+=t;

                maxf-=t;

                ret+=t;

        }

        if (maxf)lev[now]=-;

        return ret;

}

int dinic()

{

        int ret=;

        while (bfs())

        {

                ret+=dfs(sour,INF);

        }

        return ret;

}

int n,m,h;

int gid(int x,int y,int z)

{

        return +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=;k<=h;k++)

                for (i=;i<=n;i++)

                        for (j=;j<=m;j++)

                                {

                                        scanf("%d",&a[i][j][k]);

                                        addedge(gid(i,j,k-),gid(i,j,k),a[i][j][k]);

                                }

        for (i=;i<=n;i++)

                for (j=;j<=m;j++)

                        for (k=;k+d<=h;k++)

                                for (k2=;k2<;k2++)

                                        if (i+mov[k2][]> && i+mov[k2][]<=n && j+mov[k2][]> && j+mov[k2][]<=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][],j+mov[k2][],k),INF);

                                        }

        for (i=;i<=n;i++)

                for (j=;j<=m;j++)

                {

                        addedge(sour,gid(i,j,),INF);

                        addedge(gid(i,j,h),sink,INF);

                }

        printf("%d\n",dinic());

}

码农公寓