AC日记——[网络流24题]方格取数问题 cogs 734

小灰灰 2021-03-28 12:39 414阅读 0赞

# 734. \[网络流24题\] 方格取数问题 #

★★☆   输入文件：`grid.in`   输出文件：`grid.out`   简单对比  
时间限制：1 s   内存限制：128 MB

3 2 3

2 3 1

grid.out

(1<=N,M<=30)

思路：

取数；

取出的数满足任意两两坐标不相邻；

所以，我们把点标记；

把全部的点都用bfs标记成true或者false；

true与true不相邻，false与false不相邻；

然后标记为true的点在集合a；

标记为false的点在集合b；

建立超级源点s和超级汇点t；

s向a的每个点连边，流量为点的权值；

t向b的每个点连边，流量为点的权值；

然后，a中与b相邻的点连边，流量无限大；

然后求出最小割；

最后的ans等于所有点权值的总和减去最小割；

来，上代码：

#include <queue>
    #include <cstdio>
    #include <iostream>
    
    using namespace std;
    
    struct ColorNode {
        int x,y;
        bool color;
    };
    
    struct EdgeType {
        int v,f,e;
    };
    struct EdgeType edge[900000];
    
    const int dx[5]={
        0,-1,0,1,0};
    const int dy[5]={
        0,0,1,0,-1};
    
    int n,m,dis[50][50],ans,head[1001],s=0,t;
    int cnt=1,deep[1001];
    
    bool if_[50][50];
    
    char Cget;
    
    inline void in(int &now)
    {
        now=0,Cget=getchar();
        while(Cget>'9'||Cget<'0') Cget=getchar();
        while(Cget>='0'&&Cget<='9')
        {
            now=now*10+Cget-'0';
            Cget=getchar();
        }
    }
    
    struct ColorNode node(int x,int y,int color)
    {
        struct ColorNode pos;
        pos.x=x,pos.y=y,pos.color=color;
        return pos;
    }
    
    inline void edge_add(int u,int v,int f)
    {
        edge[++cnt].v=v,edge[cnt].f=f,edge[cnt].e=head[u],head[u]=cnt;
        edge[++cnt].v=u,edge[cnt].f=0,edge[cnt].e=head[v],head[v]=cnt;
    }
    
    bool BFS()
    {
        queue<int>que;
        for(int i=s;i<=t;i++) deep[i]=-1;
        deep[s]=0;que.push(s);
        while(!que.empty())
        {
            int pos=que.front();que.pop();
            for(int i=head[pos];i;i=edge[i].e)
            {
                if(deep[edge[i].v]<0&&edge[i].f>0)
                {
                    deep[edge[i].v]=deep[pos]+1;
                    if(edge[i].v==t) return true;
                    que.push(edge[i].v);
                }
            }
        }
        return false;
    }
    
    int flowing(int now,int flow)
    {
        if(now==t||flow<=0) return flow;
        int oldflow=0;
        for(int i=head[now];i;i=edge[i].e)
        {
            if(edge[i].f<=0||deep[edge[i].v]!=deep[now]+1) continue;
            int pos=flowing(edge[i].v,min(edge[i].f,flow));
            flow-=pos;
            oldflow+=pos;
            edge[i].f-=pos;
            edge[i^1].f+=pos;
            if(flow==0) return oldflow;
        }
        return oldflow;
    }
    
    int main()
    {
        freopen("grid.in","r",stdin);
        freopen("grid.out","w",stdout);
        in(n),in(m);t=n*m+1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                in(dis[i][j]);
                ans+=dis[i][j];
            }
        }
        queue<ColorNode>que;
        if_[1][1]=true;
        que.push(node(1,1,if_[1][1]));
        while(!que.empty())
        {
            struct ColorNode pos=que.front();que.pop();
            if(pos.color)
            {
                edge_add(s,(pos.x-1)*m+pos.y,dis[pos.x][pos.y]);
                int x=pos.x,y=pos.y,hash=(pos.x-1)*m+pos.y;
                for(int i=1;i<=4;i++)
                {
                    if(x+dx[i]>0&&x+dx[i]<=n&&y+dy[i]>0&&y+dy[i]<=m)
                    {
                        edge_add(hash,(pos.x+dx[i]-1)*m+pos.y+dy[i],0x7ffffff);
                    }
                }
            }
            else edge_add((pos.x-1)*m+pos.y,t,dis[pos.x][pos.y]);
            if(pos.x+1<=n&&!if_[pos.x+1][pos.y])
            {
                que.push(node(pos.x+1,pos.y,!pos.color));
                if_[pos.x+1][pos.y]=true;
            }
            if(pos.y+1<=m&&!if_[pos.x][pos.y+1])
            {
                if_[pos.x][pos.y+1]=true;
                que.push(node(pos.x,pos.y+1,!pos.color));
            }
        }
        while(BFS()) ans-=flowing(s,0x7ffffff);
        cout<<ans;
        return 0;
    }