【Gym - 101908G Gasoline】【二分答案】【网络流】【边之间有时间,求把油站填满的最小时间】

本文主要是介绍【Gym - 101908G Gasoline】【二分答案】【网络流】【边之间有时间,求把油站填满的最小时间】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

https://codeforces.com/gym/101908/problem/G

【题意】:边之间有时间,求把油站填满的最小时间

【思路】很容易想到是网络流,关键是最小时间。我们直接二分最小时间,然后如果某条边的时间比二分值小,那么就连边。然后跑最大流,看看最大流等不等于油站和,等于的话证明可行。

【代码】由于边比较多,使用dinic算法

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int n, m, k;
int sum, x[1500], y[1500], u[20020], v[20020], w[20020];
int head[2020], vis[2200], dis[2100], cur[2100], cnt;struct node{int to, flow, next;
}edge[50000];void add(int u, int v, int w){edge[cnt].to = v;edge[cnt].flow = w;edge[cnt].next = head[u];head[u] = cnt++;edge[cnt].to = u;edge[cnt].flow = 0;edge[cnt].next = head[v];head[v] = cnt++;
}int bfs(int s, int t){memset(vis, 0x7f, sizeof(vis));queue<int>q;q.push(s);vis[s] = 0;while (!q.empty()){s = q.front();q.pop();for (int i = head[s]; i != -1; i = edge[i].next){int to = edge[i].to;int flow = edge[i].flow;if (flow&&vis[to]>0x7f){vis[to] = vis[s] + 1;q.push(to);}}}if (vis[t]<inf)return 1;else return 0;
}int dfs(int s, int t, int limit){if (!limit || s == t)return limit;int flow = 0, f;for (int i = cur[s]; i != -1; i = edge[i].next){cur[s] = i;if (vis[edge[i].to] == vis[s] + 1){f = dfs(edge[i].to, t, min(limit, edge[i].flow));flow += f;limit -= f;edge[i].flow -= f;edge[i ^ 1].flow += f;if (!limit)break;}}return flow;
}int dinic(int s, int t){int ans = 0;while (bfs(s, t)){memcpy(cur, head, sizeof(head));ans += dfs(s, t, inf);}return ans;
}int build(int mid){memset(head, -1, sizeof(head));cnt = 0;for (int i = 1; i <= m; i++)//源点add(0, i, y[i]);for (int i = 1; i <= n; i++)//汇点add(i + m, m + n + 1, x[i]);for (int i = 1; i <= k; i++){if (w[i] <= mid)add(v[i], u[i] + m, inf);}int t = dinic(0, m + n + 1);if (t == sum)return 1;else return 0;
}int main(){while (~scanf("%d%d%d", &n, &m, &k)) {sum = 0;for (int i = 1; i <= n; i++) {scanf("%d", &x[i]);sum += x[i];}for (int i = 1; i <= m; i++) {scanf("%d", &y[i]);}for (int i = 1; i <= k; i++) {scanf("%d%d%d", &u[i], &v[i], &w[i]);}int l = 1, r = 1000000, ans = -1;while (l <= r) {int mid = (l + r) / 2;if (build(mid)) {r = mid - 1;ans = mid;}else l = mid + 1;}printf("%d\n", ans);}
}

 

这篇关于【Gym - 101908G Gasoline】【二分答案】【网络流】【边之间有时间,求把油站填满的最小时间】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

go中的时间处理过程

《go中的时间处理过程》:本文主要介绍go中的时间处理过程,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1 获取当前时间2 获取当前时间戳3 获取当前时间的字符串格式4 相互转化4.1 时间戳转时间字符串 (int64 > string)4.2 时间字符串转时间

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

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

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

深度解析Java项目中包和包之间的联系

《深度解析Java项目中包和包之间的联系》文章浏览阅读850次,点赞13次,收藏8次。本文详细介绍了Java分层架构中的几个关键包:DTO、Controller、Service和Mapper。_jav... 目录前言一、各大包1.DTO1.1、DTO的核心用途1.2. DTO与实体类(Entity)的区别1

Golang如何对cron进行二次封装实现指定时间执行定时任务

《Golang如何对cron进行二次封装实现指定时间执行定时任务》:本文主要介绍Golang如何对cron进行二次封装实现指定时间执行定时任务问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录背景cron库下载代码示例【1】结构体定义【2】定时任务开启【3】使用示例【4】控制台输出总结背景

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五

java Long 与long之间的转换流程

《javaLong与long之间的转换流程》Long类提供了一些方法,用于在long和其他数据类型(如String)之间进行转换,本文将详细介绍如何在Java中实现Long和long之间的转换,感... 目录概述流程步骤1:将long转换为Long对象步骤2:将Longhttp://www.cppcns.c

从基础到进阶详解Pandas时间数据处理指南

《从基础到进阶详解Pandas时间数据处理指南》Pandas构建了完整的时间数据处理生态,核心由四个基础类构成,Timestamp,DatetimeIndex,Period和Timedelta,下面我... 目录1. 时间数据类型与基础操作1.1 核心时间对象体系1.2 时间数据生成技巧2. 时间索引与数据

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

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

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