[网络流24题]方格取数

摘要:
q、 empty()){intv=q.front();q.pop();for(inti=head[v];i!=-1;i=e[i].nxt){if(e[i].cap&&dist[e[i].to]==-1)dist[e[i].to]=dist[v]+1,q.push(e[i].to);}}returndist[T]!=-1;} intdfs(intv,intf){if(v==T)returnf;intert=0;for(int[i=iter[v];i!=-1;i=e[i].nxt)if(dist[e[i].to]==dist[v]+1&&e[i].cap){intd=dfs(e[i].to,min(f,e[i].cap));e[i]-cap-=d;e[i^1].cap+=d;f-=d;ret+=d(!

Link:

P2774 传送门

Solution:

方格取数和最大且要求两两没有公共边

遇到方格内的不相邻问题,考虑黑白染色来对点分类

问题转化为使黑点不和白点相邻的最小代价,其中每个点的代价只计算一次

明显的集合划分模型,用最小割解决:

$<S,black,w>,<white,T,w>,<blakc,white,INF>$

Code:

#include <bits/stdc++.h>

using namespace std;
#define X first
#define Y second
typedef long long ll;
typedef pair<int,int> P;
const int MAXN=1e5+10,INF=1<<30;
int n,m,dat[105][105],sum;
namespace Maxflow
{
    struct edge{int nxt,to,cap;}e[MAXN<<2];
    int S,T,head[MAXN],iter[MAXN],dist[MAXN],tot=-1;
    void add_edge(int from,int to,int cap)
    {
        e[++tot].nxt=head[from];e[tot].to=to;e[tot].cap=cap;head[from]=tot;
        e[++tot].nxt=head[to];e[tot].to=from;e[tot].cap=0;head[to]=tot;
    }
    
    bool bfs()
    {
        memset(dist,-1,sizeof(dist));
        queue<int> q;q.push(S);dist[S]=0;
        while(!q.empty())
        {
            int v=q.front();q.pop();
            for(int i=head[v];i!=-1;i=e[i].nxt)
            {
                if(e[i].cap&&dist[e[i].to]==-1)
                    dist[e[i].to]=dist[v]+1,q.push(e[i].to);
            }
        }
        return dist[T]!=-1;
    }
    
    int dfs(int v,int f)
    {
        if(v==T) return f;
        int ret=0;
        for(int &i=iter[v];i!=-1;i=e[i].nxt)
            if(dist[e[i].to]==dist[v]+1&&e[i].cap)
            {
                int d=dfs(e[i].to,min(f,e[i].cap));
                e[i].cap-=d;e[i^1].cap+=d;
                f-=d;ret+=d;if(!f) break;
            }
        return ret;
    }
    
    int Dinic()
    {
        int ret=0;
        while(bfs())
        {
            for(int i=0;i<MAXN;i++) iter[i]=head[i];
            ret+=dfs(S,INF);
        }
        return ret;
    }
}
using namespace Maxflow;
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int idx(int x,int y){return (x-1)*m+y;}

int main()
{
    scanf("%d%d",&n,&m);
    S=0;T=n*m+1;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&dat[i][j]),sum+=dat[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if((i+j)%2==1) add_edge(idx(i,j),T,dat[i][j]);
            else
            {
                add_edge(S,idx(i,j),dat[i][j]);
                for(int k=0;k<4;k++)
                {
                    int fx=i+dx[k],fy=j+dy[k];
                    if(fx<1||fx>n||fy<1||fy>m) continue;
                    add_edge(idx(i,j),idx(fx,fy),INF);
                }
            }
    printf("%d",sum-Dinic());
    return 0;
}

免责声明:文章转载自《[网络流24题]方格取数》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇[Codeforces #172] TutorialPython 全栈开发:python函数进阶下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

HttpWebRequest(跨域下载文件——网络流转换为内存流下载)

1.Stream 转换为 MemoryStream(Stream不支持查找) MemoryStream StreamToMemoryStream(Stream instream) { MemoryStream outstream = newMemoryStream(); const int...

上下界网络流

目录 无源汇有上下界可行流 有源汇有上下界可行流 有源汇有上下界最大流 有源汇有上下界最小流 无源汇有上下界最小费用可行流 有源汇有上下界最小费用可行流 有源汇有上下界最小费用最大流 有源汇有上下界最小费用最小流 本篇笔记写于远古时代,写时虽然参考了一些的资料(罗列在文末),但口胡仍然占多数,准确性堪忧,如有不准确的地方,欢迎指正。 无源汇有...

Libre 6010「网络流 24 题」数字梯形 (网络流,最大费用最大流)

Libre 6010「网络流 24 题」数字梯形 (网络流,最大费用最大流) Description 给定一个由n 行数字组成的数字梯形如下图所示。梯形的第一行有m 个数字。从梯形的顶部的m 个数字开始,在每个数字处可以沿左下或右下方向移动,形成一条从梯形的顶至底的路径。规则1:从梯形的顶至底的m条路径互不相交。规则2:从梯形的顶至底的m条路径仅在数字结点处...

Luogu 2762 太空飞行计划 / Libre 6001 「网络流 24 题」太空飞行计划 (网络流,最大流)

Luogu 2762 太空飞行计划 / Libre 6001 「网络流 24 题」太空飞行计划 (网络流,最大流) Description W 教授正在为国家航天中心计划一系列的太空飞行。每次太空飞行可进行一系列商业性实验而获取利润。现已确定了一个可供选择的实验集合E={E1,E2,…,Em},和进行这些实验需要使用的全部仪器的集合I={ I1, I2,…,...

浅谈网络流的基本算法 [转]

引言 过去听起来高深莫测的网络流算法,现在已飞入寻常百姓家了,对于每一个OIER,网络流是一个神圣的东西(个人见解),但神圣的同时,它并不是那样抽象,最形象的模型就是水流,从长江源点无限的向外流水,而大海(汇点)则在不断地‘喝水’,当然,你也可以不把它想成水,或者是其他一切可以流动的东西。而事实上,有些东西的流动比较流畅,而某些东西可能相对而言比较粘稠...

[Luogu P2891/POJ 3281/USACO07OPEN ]吃饭Dining

传送门:https://www.luogu.org/problemnew/show/P2891 题面 Solution 网络流 先引用一句真理:网络流最重要的就是建模 今天这道题让我深有体会 首先,观察数据范围,n=100,一般这种100-1000的图论题,很有可能是网络流. 那就直接从网络流的角度入手 考虑这样建模 建模要点如下: 1.建权值...