Linux网络基础：从ip命令到网关DNS的排障实战
2026/10/13 4:00:46
题目描述
S 城现有两座监狱，一共关押着 N 名罪犯，编号分别为 1∼N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久，如果客观条件具备则随时可能爆发冲突。我们用“怨气值”（一个正整数值）来表示某两名罪犯之间的仇恨程度，怨气值越大，则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱，他们俩之间会发生摩擦，并造成影响力为 c 的冲突事件。
每年年末，警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表，然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力，如果影响很坏，他就会考虑撤换警察局长。
在详细考察了 N 名罪犯间的矛盾关系后，警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配，以求产生的冲突事件影响力都较小，从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨，那么他们一定会在每年的某个时候发生摩擦。
那么，应如何分配罪犯，才能使 Z 市长看到的那个冲突事件的影响力最小？这个最小值是多少？
输入格式
每行中两个数之间用一个空格隔开。第一行为两个正整数 N,M，分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 M 行每行为三个正整数 aj,bj,cj，表示 aj 号和 bj 号罪犯之间存在仇恨，其怨气值为 cj。
数据保证 1≤aj<bj≤N，0<cj≤10^9，且每对罪犯组合只出现一次。
输出格式
共一行，为 Z 市长看到的那个冲突事件的影响力。如果本年内监狱中未发生任何冲突事件，请输出 0。
输入输出样例
输入 #1复制运行
4 6 1 4 2534 2 3 3512 1 2 28351 1 3 6618 2 4 1805 3 4 12884
输出 #1复制运行
3512
说明/提示
输入输出样例说明
罪犯之间的怨气值如下面左图所示，右图所示为罪犯的分配方法，市长看到的冲突事件影响力是 3512（由 2 号和 3 号罪犯引发）。其他任何分法都不会比这个分法更优。
数据范围
对于 30% 的数据有 N≤15。
对于 70% 的数据有 N≤2×10^3，M≤5×10^4。
对于 100% 的数据有 N≤2×10^4，M≤10^5。
1. 题意转换
用一句话剥离题目的背景故事：这道题本质上是在求：给定一张带边权的无向图，要求将所有节点划分为两个互不相交的集合（对应两座监狱），使得“集合内部的所有边中，最大的边权”尽可能小。求这个“最小的最大边权”。
2. 思考过程与解题思路
第一直觉的暴力解法是什么？面对“非此即彼”的分配问题，初学者的第一直觉通常是 DFS 深度优先搜索。也就是枚举每一名罪犯：要么去 1 号监狱，要么去 2 号监狱。为什么会超时？因为每个罪犯有 2 种选择，共有 N 名罪犯，暴力枚举的时间复杂度高达 O(2^N)！结合数据范围看，N≤20000，2^20000 是一个连超级计算机都算不出来的数字，毫无疑问会立刻超时。
如何一步步推导到正解？
我们需要在题目描述中寻找“破局”的蛛丝马迹。注意这句话：“市长只会去看列表中的第一个事件（即最大的冲突）的影响力”。 这四个字“最大冲突”在疯狂地暗示我们使用贪心策略！
既然市长只看最大的那一个，我们是不是应该优先把怨气值最大的两个人分开？
贪心：我们把所有仇恨关系按照“怨气值”从大到小排序。我们顺着排好序的列表往下走，只要能分开，就把他们塞进不同的监狱。
关系维护：在分开他们的过程中，如何记录谁和谁不能在一起呢？图论中有一句极其经典的至理名言——“在只有两个阵营的情况下，敌人的敌人就是朋友。”
高光时刻：当我们顺着列表往下处理时，如果突然发现：为了把前面那些怨气值更大的人分开，当前的这两名罪犯已经被迫分到了同一座监狱里，实在分不开了！那么，此时他们俩之间的怨气值，就是我们无论如何也无法避免的“最大冲突事件”。直接输出这个值即可！
为了维护“敌人的敌人是朋友”这种传递关系，种类并查集就是我们的不二之选。
3. 算法设计与样例推演
核心算法与数据结构：本题的标准解法是：贪心排序 + 种类并查集。
结构体
node：存储每条边的起点、终点和权值，并重载<运算符实现按权值从大到小排序。并查集数组
fa[x]：维护“朋友”关系。如果两个人在同一个并查集集合中，说明他们被关在了同一座监狱。辅助数组
enemy[x]：记录罪犯 x 遇到的“第一个敌人”（因为按照贪心策略，第一个遇到的一定是怨气值最大的，必须分开）。
核心状态转移（敌人的敌人是朋友）：当处理到罪犯 u 和 v （他们之间有矛盾）时：
如果 u 已经有敌人
enemy[u]了，那 v 必须和enemy[u]关在一起，执行合并：uni(v, enemy[u])。同理，如果 v 已经有敌人
enemy[v]了，那 u 必须和enemy[v]关在一起，执行合并：uni(u, enemy[v])。
带入样例手玩推演：极简数据排序后（截取样例前 4 大）：(1,2: 28351), (3,4: 12884), (1,3: 6618), (2,3: 3512)...
处理
1 和 2：没冲突。互相记仇：enemy[1]=2,enemy[2]=1。处理
3 和 4：没冲突。互相记仇：enemy[3]=4,enemy[4]=3。处理
3 和 1 的敌人(2)成为朋友，1 和 3：没冲突。运用“敌人的敌人是朋友”：uni(3, 2)。 1 和 3 的敌人(4)成为朋友，uni(1, 4)。此时监狱状态：{1, 4} 同室，{2, 3} 同室。处理
2 和 3（怨气值 3512）：一查并查集find(2) == find(3)，发现2 和 3 的老大已经是同一个人了！说明他们已经被迫同室。直接输出3512，程序完美结束！
4. 时空复杂度分析
时间复杂度： 读入数据后，核心有两步。第一步是排序，时间复杂度为 O(MlogM)。第二步是遍历 M 条边，单次并查集操作（带有路径压缩优化）的均摊复杂度近似为 O(1)，遍历过程的时间复杂度为 O(Mα(N))。整体时间复杂度取决于排序，为O(MlogM)。对于 M=10^5 的数据，运算量在百万级别，C++ 1秒内轻松跑完。
空间复杂度： 我们需要一个大小为 10^5 的结构体数组
no存边，以及大小为 2×10^4 的fa数组和enemy数组。整体空间复杂度为O(M+N)，占用内存不到 5MB，远低于题目要求的 125MB 限制，绝对不会 MLE。
5. 坑点与易错总结
在考场上，即便你想出了正解，也有可能因为以下几个“坑点”痛失满分：
并查集忘记初始化：
fa数组必须初始化为fa[i] = i！如果不初始化，所有人的老大都是默认值 0，find函数会直接错乱。贪心策略写反：排序时重载小于号，千万别写成从小到大（
a.c < b.c）。要想清楚，我们是要优先处理最大的矛盾。天下太平特判：如果整个
for循环把所有的仇恨都处理完了，一直没有触发find(u) == find(v)，这说明这群罪犯被完美地分成了两拨，没有任何冲突！此时一定要在循环外层输出 0。find函数不加路径压缩：如果退化成一条链，每次find变成 O(N)，总时间会退化成 O(NM) 导致超时。切记写成fa[x] = find(fa[x])。
6. 完整代码
//很典型的并查集 不能直接dfs暴搜解决 #include <iostream> #include <cstring>//对应memset #include <algorithm>//对应sort using namespace std; int n,m; int fa[20010];//fa[i]为i的同监狱的老大 int enemy[20010];//enemy[i]为i遇到的第一个敌人的编号 //a和b之间存在仇恨，怨气值为c struct node{ int a; int b; int c; //按照怨气值从大到小排序 //这样我们就能优先处理最大的矛盾 尽量把他们分开 friend bool operator<(node a,node b){ return a.c>b.c; } }no[100010]; //并查集 找x的老大 int find(int x){ if(fa[x]==x) return x; //路径压缩 return fa[x]=find(fa[x]); } void uni(int u,int v){ int fau=find(u); int fav=find(v); //认v的老大为u的老大的老大 if(fau!=fav) fa[fau]=fav; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cin>>n>>m; //初始化敌对关系为空 -1代表暂时还没有敌人 memset(enemy,-1,sizeof(enemy)); //初始化自己的老大是自己 for(int i=1;i<=n;i++) fa[i]=i; //把m对罪犯关系都存进去 for(int i=1;i<=m;i++) cin>>no[i].a>>no[i].b>>no[i].c; //对no数组从大到小排序 怨气值高的优先处理 sort(no+1,no+m+1); //遍历所有罪犯关系 for(int i=1;i<=m;i++){ int u=no[i].a; int v=no[i].b; //如果u v两名罪犯的老大是同一个人 说明他们已经在同一个集合里 //则代表为了最大化满足前面那些更大怨气值的罪犯能不在一个监狱， //u v现在不得不处于同一个监狱了 if(find(u)==find(v)){ //当前的怨气值就是无法避免的最大冲突 cout<<no[i].c; return 0; } //如果u v两名罪犯的老大不是同一个人 //就先判断u和v是否有敌人 //如果u有敌人的话 就让v加入u敌人的监狱（加入同一个集合） if(enemy[u]!=-1) uni(v,enemy[u]); //如果u没有敌人 v就是他遇到的第一个（也是最大的）敌人 else enemy[u]=v; //如果v有敌人的话 就让u加入v敌人的监狱（加入同一个集合） if(enemy[v]!=-1) uni(u,enemy[v]); //如果v没有敌人 u就是他遇到的第一个（也是最大的）敌人 if(enemy[v]==-1) enemy[v]=u; } //如果全部遍历完都没有return（说明所有罪犯都被完美隔开） //即本年内监狱中未发生任何冲突事件 输出 0 cout<<0; return 0; }