HDU 3657 Game 网络流 方格取数类型

2024-05-10 12:08

本文主要是介绍HDU 3657 Game 网络流 方格取数类型,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

用模板就是爽!

#include<cstdio>
#include<cstring>
#include<iostream>
#include<iomanip>
#include<queue>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int int_max = 0x07777777;
const int int_min = 0x80000000;
const int maxn = 55*55;struct Edge{int from, to, cap, flow;Edge(int _from, int _to, int _cap, int _flow):from(_from),to(_to),cap(_cap),flow(_flow){}
};
vector<Edge> es;
vector<int> g[maxn];
int s,t,N,M,K;
int p[maxn],d[maxn],gap[maxn],cur[maxn];
void addedge (int from, int to, int cap){es.push_back(Edge(from, to, cap, 0));es.push_back(Edge(to, from, 0,0));int num = es.size();g[from].push_back(num-2);g[to].push_back(num-1);
}
void BFS (){queue<int> q;memset(d, 0, sizeof(d));d[t] = 0;q.push(t);while(!q.empty()){int u = q.front();q.pop();for(int i = 0; i < g[u].size(); i++){Edge& e = es[g[u][i]];if(e.cap==0 && d[e.to]==0){d[e.to] = d[u]+1;q.push(e.to);}}}
}
int augment (){int x = t;int a = int_max;while(x!=s){Edge& e = es[p[x]];a = (a < e.cap-e.flow ? a : e.cap-e.flow);x = es[p[x]].from;}x = t;while(x!=s){es[p[x]].flow += a;es[p[x]^1].flow -= a;x = es[p[x]].from;}return a;
}
int sap (){int flow = 0;BFS();memset(gap, 0, sizeof(gap));for(int i = 0; i <= t; i++) gap[d[i]]++;int x = s;memset(cur, 0, sizeof(cur));while(d[s] < t+1){if(x==t){flow += augment();x = s;}int ok = 0;for(int i = 0; i < g[x].size(); i++){Edge& e = es[g[x][i]];if(e.cap > e.flow && d[x]==d[e.to]+1){ok = 1;p[e.to] = g[x][i];cur[x] = i;x = e.to;break;}}if(!ok){int mm = t;for(int i = 0; i < g[x].size(); i++){Edge& e = es[g[x][i]];if(e.cap > e.flow) mm = (mm > d[e.to] ? d[e.to] : mm);}if(--gap[d[x]] == 0) break;gap[d[x]=mm+1]++;cur[x] = 0;if(x!=s) x = es[p[x]].from;}}return flow;
}int main(int argc, const char * argv[])
{while(scanf("%d %d %d", &N, &M, &K)!=EOF){int mymap[55][55];es.clear();for(int i = 0; i < maxn; i++) g[i].clear();s = N*M;t = s+1;int total = 0;for(int i = 0; i < N; i++){for(int j = 0; j < M; j++) {scanf("%d", &mymap[i][j]);total += mymap[i][j];}}int bixu[55][55];memset(bixu, 0, sizeof(bixu));for(int i = 0; i < K; i++){int x, y;scanf("%d %d", &x, &y);bixu[x-1][y-1] = 1;}int dir[4][2] = {-1,0,0,1,1,0,0,-1};for(int i = 0; i < N; i++){for(int j = 0; j < M; j++){if((i+j)&1){if(bixu[i][j]){addedge(s, i*M+j, int_max);}else{addedge(s, i*M+j, mymap[i][j]);}for(int u = 0; u < 4; u++){int ii = i + dir[u][0];int jj = j + dir[u][1];if(ii>=0 && ii<N && jj>=0 && jj<M){addedge(i*M+j, ii*M+jj, 2*(mymap[i][j]&mymap[ii][jj]));}}}else{if(bixu[i][j]){addedge(i*M+j, t, int_max);}else{addedge(i*M+j, t, mymap[i][j]);}}}}printf("%d\n", total-sap());}
}


这篇关于HDU 3657 Game 网络流 方格取数类型的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/976396

相关文章

Linux中压缩、网络传输与系统监控工具的使用完整指南

《Linux中压缩、网络传输与系统监控工具的使用完整指南》在Linux系统管理中,压缩与传输工具是数据备份和远程协作的桥梁,而系统监控工具则是保障服务器稳定运行的眼睛,下面小编就来和大家详细介绍一下它... 目录引言一、压缩与解压:数据存储与传输的优化核心1. zip/unzip:通用压缩格式的便捷操作2.

Linux网络配置之网桥和虚拟网络的配置指南

《Linux网络配置之网桥和虚拟网络的配置指南》这篇文章主要为大家详细介绍了Linux中配置网桥和虚拟网络的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、网桥的配置在linux系统中配置一个新的网桥主要涉及以下几个步骤:1.为yum仓库做准备,安装组件epel-re

python如何下载网络文件到本地指定文件夹

《python如何下载网络文件到本地指定文件夹》这篇文章主要为大家详细介绍了python如何实现下载网络文件到本地指定文件夹,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下...  在python中下载文件到本地指定文件夹可以通过以下步骤实现,使用requests库处理HTTP请求,并结合o

Linux高并发场景下的网络参数调优实战指南

《Linux高并发场景下的网络参数调优实战指南》在高并发网络服务场景中,Linux内核的默认网络参数往往无法满足需求,导致性能瓶颈、连接超时甚至服务崩溃,本文基于真实案例分析,从参数解读、问题诊断到优... 目录一、问题背景:当并发连接遇上性能瓶颈1.1 案例环境1.2 初始参数分析二、深度诊断:连接状态与

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理(处理粘包/拆包)3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

Pydantic中Optional 和Union类型的使用

《Pydantic中Optional和Union类型的使用》本文主要介绍了Pydantic中Optional和Union类型的使用,这两者在处理可选字段和多类型字段时尤为重要,文中通过示例代码介绍的... 目录简介Optional 类型Union 类型Optional 和 Union 的组合总结简介Pyd

Oracle数据库常见字段类型大全以及超详细解析

《Oracle数据库常见字段类型大全以及超详细解析》在Oracle数据库中查询特定表的字段个数通常需要使用SQL语句来完成,:本文主要介绍Oracle数据库常见字段类型大全以及超详细解析,文中通过... 目录前言一、字符类型(Character)1、CHAR:定长字符数据类型2、VARCHAR2:变长字符数

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.