当前位置:网站首页>Network Saboteur
Network Saboteur
2022-08-10 13:18:00 【51CTO】
Problem Description
A university network is composed of N computers. System administrators gathered information on the traffic between nodes, and carefully divided the network into two subnetworks in order to minimize traffic between parts.
A disgruntled computer science student Vasya, after being expelled from the university, decided to have his revenge. He hacked into the university network and decided to reassign computers to maximize the traffic between two subnetworks.
Unfortunately, he found that calculating such worst subdivision is one of those problems he, being a student, failed to solve. So he asks you, a more successful CS student, to help him.
The traffic data are given in the form of matrix C, where Cij is the amount of data sent between ith and jth nodes (Cij = Cji, Cii = 0). The goal is to divide the network nodes into the two disjointed subsets A and B so as to maximize the sum ∑Cij (i∈A,j∈B).
Input
The first line of input contains a number of nodes N (2 <= N <= 20). The following N lines, containing N space-separated integers each, represent the traffic matrix C (0 <= Cij <= 10000). <br>Output file must contain a single integer -- the maximum traffic between the subnetworks. <br>
Output
Output must contain a single integer -- the maximum traffic between the subnetworks.
Sample Input
Sample Output
Many points are directly distant,Divide the points into two-sum sets,The division method of the largest of the two sets.
思路:
用dfs()Repeatedly divide the points into two sets.
代码:
边栏推荐
- 「网络架构」网络代理第一部分: 代理概述
- 海外邮件发送指南(二)
- 查看 CUDA cudnn 版本 & 测试 cuda 和 cudnn 有效性「建议收藏」
- G1和CMS的三色标记法及漏标问题
- OTA自动化测试解决方案---整体方案介绍
- Ethernet channel Ethernet channel
- Merge similar items in LeetCode simple questions
- AtCoder初学者比赛077 D -小多
- Keithley DMM7510 accurate measurement of ultra-low power consumption equipment all kinds of operation mode power consumption
- Nanodlp v2.2/v3.0光固化电路板,机械开关/光电开关/接近开关的接法和系统状态电平设置
猜你喜欢
来看Prada大秀吗?在元宇宙里那种!
DNS欺骗-教程详解
ArcMAP出现-15的问题无法访问[Provide your license server administrator with the following information:Err-15]
金山云要飘到哪里?
神经网络可视化有3D版本了,美到沦陷!(已开源)
Custom filters and interceptors implement ThreadLocal thread closure
Shell:数组
Polygon zkEVM工具——PIL和CIRCOM
Nanodlp v2.2/v3.0 light curing circuit board, connection method of mechanical switch/photoelectric switch/proximity switch and system state level setting
bgp双平面实验 路由策略控制流量
随机推荐
sprintboot项目通过interceptor和filter实现接入授权控制
友邦人寿可观测体系设计与落地
MySQL面试题——MySQL常见查询
【论文+代码】PEBAL/Pixel-wise Energy-biased Abstention Learning for Anomaly Segmentation on Complex Urban Driving Scenes(复杂城市驾驶场景异常分割的像素级能量偏置弃权学习)
浙大、阿里提出DictBERT,字典描述知识增强的预训练语言模型
“68道 Redis+168道 MySQL”精品面试题(带解析)
【jstack、jps命令使用】排查死锁
查看 CUDA cudnn 版本 & 测试 cuda 和 cudnn 有效性「建议收藏」
Prada, big show?In the yuan in the universe that!
Pod生命周期
ASP.NET Core依赖注入系统学习教程:ServiceDescriptor(服务注册描述类型)
Reversing words in a string in LeetCode
想通这点,治好 AI 打工人的精神内耗
【mysql索引实现原理】
Comparison version number of middle questions in LeetCode
【百度统计】用户行为分析
Requirements for the construction of Loudi stem cell preparation laboratory
LeetCode中等题之颠倒字符串中的单词
【数字IC验证进阶】SoC系统验证和IP模块验证的区别及侧重点分析
[Advanced Digital IC Verification] Difference and focus analysis between SoC system verification and IP module verification