「HNOI2013」切糕

题目链接

\(Solution\)

对于这道题，我们首先来看看没有\(D\)这个约束的该如何做。

我们考虑构造最小割模型。

其实直接贪心就好了,选出每条路径上的最小值就好了(路径就是将每层的同一个点连起来)

但是因为这题不仅仅是这样,还有一些约束条件需要满足。所以还是看看如何建模吧。

其实和贪心很像啊。

首先如上面所说连成一条条路径，在将第一层和\(S\)相连,最后一层和\(T\)连接。跑一遍最小割就好了。至于流量，这个自己应该知道吧,如果不知道来看看图，更加深刻的理解。(这里只选了局部图,有点丑)

首先我们将第\(k\)层第\(i\)行,第\(j\)列的数的值设为\(V[k][i][j]\)

现在考虑一下\(D\)的约束条件

我们可以对于一个点，令他为\((k,x,y)\)，我们可以将点x连向\(k-D\)层中与\((x,y)\)相邻的点,流量为\(inf\),这样就可以满足条件了，至于为什么来借助图来看一下吧。

假设现在\(D=1\),如图:

我们将\(i\)点到\(j\)点的边表示为\(f[i][j]\)

我们首先的思考一下，每一条链只能割一条边，因为如果割多条明显不会最优。假设我们现在割的是\(f[6][8]\)这一条边,那么我们就不能割\(f[S][1]\),我们将\((6,1)\)连一条为\(inf\)的边我这样当我们割掉是\(f[6][8]\)，则这一条道路走不通我们就会走\(f[6][1]\)因为要满足最优，所以我们一定不会割\(f[S][1]\),其他的同理。

\(Code\)

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define inf 1e9

using namespace std;

typedef long long ll;

int read(){

    int x=0,f=1;char c=getchar();

    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();

    return x*f;

}

struct node{

    int to,next,v;

}a[200001];

int head[100001],cnt,n,m,s,t,x,y,z,dep[100001];

void add(int x,int y,int c){

    a[++cnt].to=y,a[cnt].next=head[x],a[cnt].v=c,head[x]=cnt;

    a[++cnt].to=x,a[cnt].next=head[y],a[cnt].v=0,head[y]=cnt;

}

queue<int> q;

int bfs(){

    memset(dep,0,sizeof(dep));

    q.push(s);

    dep[s]=1;

    while(!q.empty()){

        int now=q.front();

        q.pop();

        for(int i=head[now];i;i=a[i].next){

            int v=a[i].to;

            if(!dep[v]&&a[i].v>0)

                dep[v]=dep[now]+1,q.push(v);

        }

    }

    if(dep[t])

        return 1;

    return 0;

}

int dfs(int k,int list){

    if(k==t||!list)

        return list;

    for(int i=head[k];i;i=a[i].next){

        int v=a[i].to;

        if(dep[v]==dep[k]+1&&a[i].v>0){

            int p=dfs(v,min(list,a[i].v));

            if(p){

                a[i].v-=p;

                if(i&1)

                    a[i+1].v+=p;

                else a[i-1].v+=p;

                return p;

            }

        }

    }

    dep[k]=0;

    return 0;

}

int Dinic(){

    int ans=0,k;

    while(bfs())

        while((k=dfs(s,inf)))

            ans+=k;

    return ans;

}

int V[50][50][50],vis[50][50][50];

int fx[5]={0,1,-1,0,0};

int fy[5]={0,0,0,1,-1};

int main(){

    int P=read(),Q=read(),R=read(),D=read(),tot=0;

    t=P*Q*R+1;

    for(int k=1;k<=R;k++)

        for(int i=1;i<=P;i++)

            for(int j=1;j<=Q;j++)

                V[k][i][j]=read(),vis[k][i][j]=++tot;

    for(int k=D+1;k<=R;k++)

        for(int i=1;i<=P;i++)

            for(int j=1;j<=Q;j++)

                for(int z=1;z<=4;z++){

                    x=i+fx[z],y=j+fy[z];

                    if(x<1||x>P||y<1||y>Q) continue;

                    add(vis[k][i][j],vis[k-D][x][y],inf);

            }

    for(int k=2;k<=R;k++)

        for(int i=1;i<=P;i++)

            for(int j=1;j<=Q;j++)

                add(vis[k-1][i][j],vis[k][i][j],V[k][i][j]);

    for(int i=1;i<=P;i++)

        for(int j=1;j<=Q;j++)

            add(s,vis[1][i][j],V[1][i][j]),add(vis[R][i][j],t,inf);

    printf("%d",Dinic());

}

巴特西

「HNOI2013」切糕

题目链接

\(Solution\)

\(Code\)

最新文章

热门文章