[网络流24题#9] [cogs734] 方格取数 [网络流,最大流最小割]
2024-08-31 03:09:41
将网格分为两部分,方法是黑白染色,即判断(i+j)&1即可,分开后从白色格子向黑色格子连边,每个点需要四条(边界点可能更少),也就是每个格子周围的四个方向。之后将源点和汇点分别于黑白格子连边,边权即为点权,最后用总权值减去最小割即可。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <queue> using namespace std; #define INF 0x3f3f3f3f template<const int _n,const int _m>
struct Edge
{
struct Edge_base { int to,next,w; }e[_m]; int cnt,p[_n];
Edge() { clear(); }
void insert(const int x,const int y,const int z)
{ e[++cnt].to=y; e[cnt].next=p[x]; e[cnt].w=z; p[x]=cnt; return ; }
int start(const int x) { return p[x]; }
void clear() { cnt=,memset(p,,sizeof(p)); }
Edge_base& operator[](const int x) { return e[x]; }
}; int n,m,N,SSS,TTT,a[][];
int level[],cur[];
Edge<,> e; bool Bfs(const int S)
{
int i,t;
queue<int> Q;
memset(level,,sizeof(level));
level[S]=;
Q.push(S);
while(!Q.empty())
{
t=Q.front(),Q.pop();
for(i=e.start(t);i;i=e[i].next)
{
if(!level[e[i].to] && e[i].w)
{
level[e[i].to]=level[t]+;
Q.push(e[i].to);
}
}
}
return level[TTT];
} int Dfs(const int S,const int bk)
{
if(S==TTT)return bk;
int rest=bk;
for(int &i=cur[S];i;i=e[i].next)
{
if(level[e[i].to]==level[S]+ && e[i].w)
{
int flow=Dfs(e[i].to,min(e[i].w,rest));
e[i].w-=flow;
e[i^].w+=flow;
if((rest-=flow)<=)break;
}
}
if(bk==rest)level[S]=;
return bk-rest;
} int Dinic()
{
int flow=;
while(Bfs(SSS))
{
memcpy(cur,e.p,sizeof(cur));
flow+=Dfs(SSS,0x3f3f3f3f);
}
return flow;
} int main()
{
freopen("grid.in","r",stdin);
freopen("grid.out","w",stdout); int i,j,Sum=; scanf("%d%d",&n,&m);
N=n*m;SSS=N+,TTT=SSS+;
for(i=;i<=n;++i)for(j=;j<=m;++j)
scanf("%d",&a[i][j]),Sum+=a[i][j];
for(i=;i<=n;++i)
{
for(j=;j<=m;++j)
{
int t=(i-)*m+j;
if(((i&) && !(j&)) || (!(i&) && (j&)))
{
e.insert(SSS,t,a[i][j]);
e.insert(t,SSS,);
if(i>)e.insert(t,t-m,INF),e.insert(t-m,t,);
if(i<n)e.insert(t,t+m,INF),e.insert(t+m,t,);
if(j>)e.insert(t,t-,INF),e.insert(t-,t,);
if(j<m)e.insert(t,t+,INF),e.insert(t+,t,);
}
else
{
e.insert(t,TTT,a[i][j]);
e.insert(TTT,t,);
if(i>)e.insert(t-m,t,INF),e.insert(t,t-m,);
if(i<n)e.insert(t+m,t,INF),e.insert(t,t+m,);
if(j>)e.insert(t-,t,INF),e.insert(t,t-,);
if(j<m)e.insert(t+,t,INF),e.insert(t,t+,);
}
}
} printf("%d\n",Sum-Dinic()); return ;
}
最新文章
- tp框架,访问方式、空方法
- JavaScript高级程序设计-(2)基础概念
- maven更改编译环境的java版本
- 如何在EF CodeFirst中使用唯一约束(Unique)
- Linux 进程管理器 supervixor
- Win7-64bit系统下安装mysql的ODBC驱动
- transform: translateY(-50%) 实现元素垂直居中效果
- 9月java货车版速记
- android部分手机onclick事件触发2次
- ElastciSearch常用APi
- Oracle基本分组查询group by的使用
- 用到的Python运算符
- DES加密解密 与 Cookie的封装(C#与js互相加密解密)
- CentOS 6.5 开机启动指定服务
- json解析—Gson以及GsonFormat插件的运用
- shell 脚本示例
- Python监控服务器利器--psutil
- visual studio的试用版评估期已结束 解决办法
- 必修3第三章概率mindmaps
- Unity 游戏开发技巧集锦之创建部分光滑部分粗糙的材质