2279. 网络战争(最小割,01分数规划,二分)

2024-02-27 17:04

本文主要是介绍2279. 网络战争(最小割,01分数规划,二分),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

活动 - AcWing

给出一个带权无向图 G=(V,E),每条边 e 有一个权 we。

求将点 s 和点 t 分开的一个边割集 C,使得该割集的平均边权最小,即最小化:

∑(e∈C)we/|C|

注意: 边割集的定义与最小割中的割边的集合不同。在本题中,一个边割集是指:将这些边删去之后,s 与 t 不再连通。

输入格式

第一行包含四个整数 n,m,s,t,其中 n,m 分别表示无向图的点数、边数。

接下来 m 行,每行包含三个整数 a,b,w,表示点 a 和 b 之间存在一条无向边,边权为 w。

点的编号从 1 到 n。

输出格式

输出一个实数,表示将点 s 和点 t 分开的边割集的最小平均边权。

结果保留两位小数。

数据范围

2≤n≤100,
1≤m≤400,
1≤w≤107
保证 s 和 t 之间连通。

输入样例:
6 8 1 6
1 2 3
1 3 3
2 4 2
2 5 2
3 4 2
3 5 2
5 6 3
4 6 3
输出样例:
2.00

解析: 

01分数规划:上一篇题解有详细讲解,361. 观光奶牛(小数二分,spfa判断正环,01分数规划)-CSDN博客。

 

本题要求的是∑(e∈C)we/|C| 的最小值。这种形式的问题基本都需要用到 01 分数规划。

现在取一个值 x,然后我们看一下 ∑(e∈C)we/|C| 和 x 的关系。

假设现在 ∑(e∈C)we/|C|>x,通过变形得到 ∑(e∈C)we−|C|⋅x>0,由于 ∑e∈Cwe 和 x 都有 |C| 个,因此进一步化简为 ∑e∈C(we−x)>0。

假设现在 ∑e∈Cwe|C|<x,同样可以得到 ∑e∈C(we−x)<0。

因此我们可以根据 ∑e∈C(we−x) 和 0 的关系来判断 ∑e∈Cwe|C| 和 x 的关系。而这个关系是有二段性的,是可以进行二分的。

在整个范围区间内进行二分,二分出的中间值就是 x,如果 ∑e∈C(we−x)>0,说明∑e∈Cwe|C|>x,继续二分右区间。否则说明 ∑e∈Cwe|C|<x,继续二分左区间。最终得到一个固定值,就是答案。

每次需要求出 ∑e∈C(we−x),我们可以建一个新图,将所有边都减去 x,在新图中求一个边割集的权值和就是 ∑e∈C(we−x)。

那么新图中可能存在 we−x≤0,对于这样的边,我们一定要选上,因为一个边割集若加上一些无法让图重新连上的边,它仍然是一个边割集,但是权值和会变小,所以这种负权值边必选。

现在已经选上所有非正边,我们需要考虑一下剩下的边该怎么选,因为边割集和流网络的割是不一样的,边割集在有流网络的割的所有边的同时,在这两个集合里面还有一些边,这些边去掉之后也能让整张图不连通,由于剩下要考虑的边都是正边,我们要让权值和越小,因此这两个集合里面的边尽量能不选就不选,因此在权值和最小的情况下,边割集一定不包含所有集合里面的边了,这时就是只剩下两个集合之间的边了,而这些边的权值和其实就是流网络的割。

通过以上的分析,我们成功将每个边割集的权值和与流网络的割的边的容量和对应起来。而边割集的最小权值和就是割的最小容量和,即最小割。

然后本题是无向图,而流网络中是有向图,我们需要将有向图和无向图对应起来,我们只需要正常建两条有向边,来回的流量会被抵消,而且流网络的割有一个特点就是保证正向边是满流反向边是 0 流,所以无向图的割等价于有向图的割,不需要额外处理。

然后这里每条无向边建两条有向边,有向边在残量网络中又有反向边,所以每条无向边都要建四条边,这里和前面的某一题一样直接合并成两条边即可。

最终得出本题算法,二分找最小值,每次求一遍最小割继续二分。

作者:小小_88
链接:https://www.acwing.com/solution/content/128176/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

 

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 1e4 + 5, M = 1e5 * 2 + 10, INF = 0x3f3f3f3f;
const double eps = 1e-8;
int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
double f[M];
int q[N], d[N], cur[N];void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;e[idx] = a, w[idx] = c, ne[idx] = h[b], h[b] = idx++;
}bool bfs() {int hh = 0, tt = 0;memset(d, -1, sizeof d);q[0] = S, d[S] = 0, cur[S] = h[S];while (hh <= tt) {int t = q[hh++];for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];if (d[j] == -1 && f[i]) {d[j] = d[t] + 1;cur[j] = h[j];if (j == T)return 1;q[++tt] = j;}}}return 0;
}double find(int u, double limit) {if (u == T)return limit;double flow=0;for (int i = cur[u]; i != -1 && flow < limit; i = ne[i]) {int j = e[i];cur[u] = i;if (d[j] == d[u] + 1 && f[i]) {double t = find(j, min(limit - flow, f[i]));if (!t)d[j] = -1;f[i] -= t, f[i ^ 1] += t, flow += t;}}return flow;
}double dinic(double mid) {double ret = 0;for (int i = 0; i < idx; i += 2) {if (w[i] <= mid) {ret += w[i] - mid;f[i] = f[i ^ 1] = 0;}else f[i] = f[i ^ 1] = w[i] - mid;}double r = 0, flow;while (bfs())while (flow = find(S, INF))r += flow;return r + ret;
}int main() {cin >> n >> m >> S >> T;memset(h, -1, sizeof h);for (int i = 1,a,b,c; i <= m; i++) {scanf("%d%d%d", &a, &b, &c);add(a, b, c);}double l = 0, r = 1e7;double mid;while (r - l > eps) {mid = (r + l) / 2;if (dinic(mid) < 0)r = mid;else l = mid;}printf("%.2lf\n", r);return 0;
}

这篇关于2279. 网络战争(最小割,01分数规划,二分)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

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.

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爬虫开发发送请求解

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

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

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

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

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

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

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu2289(简单二分)

虽说是简单二分,但是我还是wa死了  题意:已知圆台的体积,求高度 首先要知道圆台体积怎么求:设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下: #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ