BZOJ 1324 Exca神剑 最小割

标题效果：给定一个n*m矩阵。所有的格宝石之子，人们可选择起始位置，后除去宝石的当前位置的周围消失，然后你就可以走两步，重复上述过程

easy发现格儿子把它周围格孩子不能拿 因此，党格访问问题

黑白染色 黑色点连源 白色点连汇 流量为格子的权值 黑白之间连边 流量为正无穷 用总和减去最大流就是答案

曾经写的EK 跑了4000+ms我也是醉了

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#define M 110

#define MAX (0x7fffffff)

int m,n,sum,ans;

struct abcd{int x,y,f,next;}table[100100];int head[M][M],tot=1;

void addd(int x,int y,int tox,int toy,int f)

{

    table[++tot].x=tox;

    table[tot].y=toy;

    table[tot].f=f;

    table[tot].next=head[x][y];

    head[x][y]=tot;

}

void add(int x,int y,int tox,int toy,int f){ addd(x,y,tox,toy,f);addd(tox,toy,x,y,0); }

inline int min(int x,int y){ return x<y?x:y; }

struct que{int x,y;}q[65540];unsigned short r,h;

int f[M][M],from[M][M];

bool maxflow()

{

    int i;

    memset(f,0,sizeof f);

    q[++h].x=0;q[h].y=0;

    f[0][0]=MAX;

    while(r!=h)

    {

        r++;

        for(i=head[q[r].x][q[r].y];i;i=table[i].next)if(table[i].f)if(!f[table[i].x][table[i].y])

        {

            f[table[i].x][table[i].y]=min(f[q[r].x][q[r].y],table[i].f);

            from[table[i].x][table[i].y]=i;

            q[++h].x=table[i].x;q[h].y=table[i].y;

        }

    }

    if(!f[0][1])return 0;

    ans+=f[0][1];

    for(i=from[0][1];i;i=from[table[i^1].x][table[i^1].y])table[i].f-=f[0][1],table[i^1].f+=f[0][1];

    return 1;

}

int main()

{

    int i,j,x;

    scanf("%d%d",&m,&n);

    for(i=1;i<=m;i++)

    for(j=1;j<=n;j++)

    {

        scanf("%d",&x);

        sum+=x;

        if(i+j&1)add(i,j,0,1,x);

        else

        {

            add(0,0,i,j,x);

            if(i^1)add(i,j,i-1,j,MAX);

            if(j^1)add(i,j,i,j-1,MAX);

            if(i^m)add(i,j,i+1,j,MAX);

            if(j^n)add(i,j,i,j+1,MAX);

        }

    }

    while(maxflow());

    printf("%d",sum-ans);

}

版权声明：本文博主原创文章。博客，未经同意不得转载。