Network Saboteur/网络破坏者

：初心～亦是~

于 2021-07-05 14:58:24 发布

阅读量355

点赞数

分类专栏： bfs 文章标签：算法

本文链接：https://blog.csdn.net/cloud_sea0724/article/details/118488535

版权

bfs 专栏收录该内容

2 篇文章

订阅专栏

该博客讨论了一道计算机科学问题，涉及网络节点的划分以最大化子网间流量。问题中，一个被开除的学生试图通过重新分配计算机来增加流量，而你需要帮助找到最佳的子网划分策略。这个问题通过深度优先搜索（DFS）来解决，确保找到流量最大的子网组合。解决方案中，使用了回溯法来尝试不同的节点分配，以达到流量最大化。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

项目场景：

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).

题意主要是说：一个大学网络由N台计算机组成。系统管理员收集节点之间的流量信息，并小心地将网络划分为两个子网，以尽量减少各部分之间的流量。心怀不满的计算机科学专业学生 Vasya 在被大学开除后决定报复。他入侵了大学网络并决定重新分配计算机以最大化两个子网之间的流量。不幸的是，他发现计算这种最糟糕的细分是他作为一名学生未能解决的问题之一。所以他请你，一个更成功的 CS 学生，帮助他。流量数据以矩阵 C 的形式给出，其中 Cij 是第 i 个和第 j 个节点之间发送的数据量（Cij = Cji，Cii = 0）。目标是将网络节点划分为两个不相交的子集 A 和 B，从而使总和 ∑Cij (i∈A,j∈B) 最大化。

也就是说要将网络节点划分为两个不相交的子集A和B，比如一共有4个节点，即1，2，3，4.那么A集合为1，B集合为2，3，4.那么组成的队为(1,2),(1,3),(1,4).如果将2从B集合移入A集合，那么现在的队为(1,3),(1,4),(2,3),(2,4).比起之前2还没有移动的时候，两者相差了(1,2)，(2,3),(2,4)，从第一步开始计算的sum而言，sum=sum-(1,2)+(2,3)+(2,4)才会达到第二部的sum真实数据。从此以下类推。

输入

3
0 50 30
50 0 40
30 40 0

输出

90

问题描述：

提示：在这道题中，得到的结果屡次得到80，以至于怀疑自己的理解，后来加了回溯，结果就对了，٩(๑^o^๑)۶。因为在某层的问题解决之后，再将标记数组重置，又重新往A集合中加入一个新数,并取回之前的数。比如上面说的，将2从B集合转移至A集合，但也有可能是将3从B集合转移至A集合内，即第一步为(1,2),(1,3),(1,4)。第二步为(1,2),(1,4),(3,2),(3,4)。那么sum=sum-(1,3)+(3,2)+(3,4)。所以这个时候就需要将标记数组回溯为原来的数。

解决方案：

#include<bits/stdc++.h>
using namespace std;
int s[22][22]= {0},c[22]= {0},n,ans=0;//将其初始化
void dfs(int x,int sum) {
	c[x]=1;//赋值标记数组
	for(int i=0; i<n; i++) {
		if(c[i])
			sum-=s[x][i];//减去多余的数，比如(1,2),(1,3)......
		else
			sum+=s[x][i];//加上缺少的数，比如(3,2)+(3,4),(2,3)+(2,4)......
	}
	ans=max(ans,sum);//将最大值取出


	for(int i=x+1; i<=n; i++) {
		dfs(x+1,sum);
		c[i]=0;
	}
}
int main() {
	scanf("%d",&n);
	for(int i=0; i<n; i++)
		for(int j=0; j<n; j++)
			cin>>s[i][j];
	dfs(0,0);
	cout<<ans<<endl;
	return 0;
}