poj 3068 有流量限制的最小费用网络流

2024-09-09 15:58

本文主要是介绍poj 3068 有流量限制的最小费用网络流,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:

m条有向边连接了n个仓库,每条边都有一定费用。

将两种危险品从0运到n-1,除了起点和终点外,危险品不能放在一起,也不能走相同的路径。

求最小的费用是多少。


解析:

抽象出一个源点s一个汇点t,源点与0相连,费用为0,容量为2。

汇点与n - 1相连,费用为0,容量为2。

每条边之间也相连,费用为每条边的费用,容量为1。

建图完毕之后,求一条流量为2的最小费用流就行了。


代码:

#pragma comment(linker, "/STACK:1677721600")
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#define pb push_back
#define mp make_pair
#define LL long long
#define lson lo,mi,rt<<1
#define rson mi+1,hi,rt<<1|1
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define mem(a,b) memset(a,b,sizeof(a))
#define FIN freopen("in.txt", "r", stdin)
#define FOUT freopen("out.txt", "w", stdout)using namespace std;
const int mod = 1e9 + 7;
const double eps = 1e-8;
const double ee = exp(1.0);
const int inf = 0x3f3f3f3f;
const int maxn = 100 + 10;
const double pi = acos(-1.0);
const LL iinf = 0x3f3f3f3f3f3f3f3f;//firs - 最短距离  second 顶点编号
typedef pair<int, int> P;struct Edge
{int to, cap, cost, rev;Edge() {}Edge(int _to, int _cap, int _cost, int _rev){to = _to;cap = _cap;cost = _cost;rev = _rev;}
};int V;//顶点数
vector<Edge> g[maxn];       //图的邻接表
int h[maxn];                //残量
int dist[maxn];             //最短距离
int preV[maxn], preE[maxn]; //前驱节点 以及对于的边void init()
{for (int i = 0; i <= V; i++){g[i].clear();}
}//向图中增加一条从fr到to容量为cap费用为cost的边
void addEdge(int fr, int to, int cap, int cost)
{g[fr].push_back(Edge(to, cap, cost, g[to].size()));g[to].push_back(Edge(fr, 0, -cost, g[fr].size() - 1));
}//求解从s到t流量为f的最小费用流
//没有流量为f的流,返回-1
int minCostFlow(int s, int t, int f)
{int res = 0;memset(h, 0, sizeof(h));while (f > 0){priority_queue<P, vector<P>, greater<P> > q;memset(dist, inf, sizeof(dist));dist[s] = 0;q.push(P(0, s));while (!q.empty()){P now = q.top();q.pop();int v = now.second;if (dist[v] < now.first)continue;for (int i = 0; i < g[v].size(); i++){Edge& e = g[v][i];if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]){dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];preV[e.to] = v;preE[e.to] = i;q.push(P(dist[e.to], e.to));}}}if (dist[t] == inf){return -1;}for (int v = 0; v < V; v++)h[v] += dist[v];int d = f;for (int v = t; v != s; v = preV[v]){d = min(d, g[preV[v]][preE[v]].cap);}f -= d;res += d * h[t];for (int v = t; v != s; v = preV[v]){Edge& e = g[preV[v]][preE[v]];e.cap -= d;g[v][e.rev].cap += d;}}return res;
}int main()
{
#ifdef LOCALFIN;
#endif // LOCALint n, m;int ca = 1;while (~scanf("%d%d", &n, &m)){if (!n && !m)break;int s = 0, t = n + 1;V = t + 1;init();addEdge(s, 1, 2, 0);addEdge(n, n + 1, 2, 0);for (int i = 0; i < m; i++){int fr, to, cost;scanf("%d%d%d", &fr, &to, &cost);fr++, to++;addEdge(fr, to, 1, cost);}int ans = minCostFlow(s, t, 2);printf("Instance #%d: ", ca++);if (ans == -1)puts("Not possible");elseprintf("%d\n", ans);}return 0;
}


这篇关于poj 3068 有流量限制的最小费用网络流的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

浅谈mysql的sql_mode可能会限制你的查询

《浅谈mysql的sql_mode可能会限制你的查询》本文主要介绍了浅谈mysql的sql_mode可能会限制你的查询,这个问题主要说明的是,我们写的sql查询语句违背了聚合函数groupby的规则... 目录场景:问题描述原因分析:解决方案:第一种:修改后,只有当前生效,若是mysql服务重启,就会失效;

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》:本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解

Nginx如何进行流量按比例转发

《Nginx如何进行流量按比例转发》Nginx可以借助split_clients指令或通过weight参数以及Lua脚本实现流量按比例转发,下面小编就为大家介绍一下两种方式具体的操作步骤吧... 目录方式一:借助split_clients指令1. 配置split_clients2. 配置后端服务器组3. 配

如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解

《如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解》:本文主要介绍如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别的相关资料,描述了如何使用海康威视设备网络SD... 目录前言开发流程问题和解决方案dll库加载不到的问题老旧版本sdk不兼容的问题关键实现流程总结前言作为

使用zabbix进行监控网络设备流量

《使用zabbix进行监控网络设备流量》这篇文章主要为大家详细介绍了如何使用zabbix进行监控网络设备流量,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录安装zabbix配置ENSP环境配置zabbix实行监控交换机测试一台liunx服务器,这里使用的为Ubuntu22.04(

SSID究竟是什么? WiFi网络名称及工作方式解析

《SSID究竟是什么?WiFi网络名称及工作方式解析》SID可以看作是无线网络的名称,类似于有线网络中的网络名称或者路由器的名称,在无线网络中,设备通过SSID来识别和连接到特定的无线网络... 当提到 Wi-Fi 网络时,就避不开「SSID」这个术语。简单来说,SSID 就是 Wi-Fi 网络的名称。比如

Java实现任务管理器性能网络监控数据的方法详解

《Java实现任务管理器性能网络监控数据的方法详解》在现代操作系统中,任务管理器是一个非常重要的工具,用于监控和管理计算机的运行状态,包括CPU使用率、内存占用等,对于开发者和系统管理员来说,了解这些... 目录引言一、背景知识二、准备工作1. Maven依赖2. Gradle依赖三、代码实现四、代码详解五

SpringBoot实现基于URL和IP的访问频率限制

《SpringBoot实现基于URL和IP的访问频率限制》在现代Web应用中,接口被恶意刷新或暴力请求是一种常见的攻击手段,为了保护系统资源,需要对接口的访问频率进行限制,下面我们就来看看如何使用... 目录1. 引言2. 项目依赖3. 配置 Redis4. 创建拦截器5. 注册拦截器6. 创建控制器8.