[NOIP 2010 提高组] 关押罪犯（洛谷-P1525）

题目描述S 城现有两座监狱一共关押着 N 名罪犯编号分别为 1∼N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久如果客观条件具备则随时可能爆发冲突。我们用“怨气值”一个正整数值来表示某两名罪犯之间的仇恨程度怨气值越大则这两名罪犯之间的积怨越多。如果两名怨气值为 c 的罪犯被关押在同一监狱他们俩之间会发生摩擦并造成影响力为 c 的冲突事件。每年年末警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表然后上报到 S 城 Z 市长那里。公务繁忙的 Z 市长只会去看列表中的第一个事件的影响力如果影响很坏他就会考虑撤换警察局长。在详细考察了 N 名罪犯间的矛盾关系后警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配以求产生的冲突事件影响力都较小从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨那么他们一定会在每年的某个时候发生摩擦。那么应如何分配罪犯才能使 Z 市长看到的那个冲突事件的影响力最小这个最小值是多少输入格式每行中两个数之间用一个空格隔开。第一行为两个正整数 N,M分别表示罪犯的数目以及存在仇恨的罪犯对数。接下来的 M 行每行为三个正整数 aj​,bj​,cj​表示 aj​ 号和 bj​ 号罪犯之间存在仇恨其怨气值为 cj​。数据保证 1≤aj​bj​≤N0cj​≤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^3M≤5×10^4。对于 100% 的数据有 N≤2×10^4M≤10^5。1. 题意转换用一句话剥离题目的背景故事这道题本质上是在求给定一张带边权的无向图要求将所有节点划分为两个互不相交的集合对应两座监狱使得“集合内部的所有边中最大的边权”尽可能小。求这个“最小的最大边权”。2. 思考过程与解题思路第一直觉的暴力解法是什么面对“非此即彼”的分配问题初学者的第一直觉通常是 DFS 深度优先搜索。也就是枚举每一名罪犯要么去 1 号监狱要么去 2 号监狱。为什么会超时因为每个罪犯有 2 种选择共有 N 名罪犯暴力枚举的时间复杂度高达 O(2^N)结合数据范围看N≤200002^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。处理1 和 3没冲突。运用“敌人的敌人是朋友”3 和 1 的敌人(2)成为朋友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)。对于 M10^5 的数据运算量在百万级别C 1秒内轻松跑完。空间复杂度 我们需要一个大小为 10^5 的结构体数组no存边以及大小为 2×10^4 的fa数组和enemy数组。整体空间复杂度为O(MN)占用内存不到 5MB远低于题目要求的 125MB 限制绝对不会 MLE。5. 坑点与易错总结在考场上即便你想出了正解也有可能因为以下几个“坑点”痛失满分并查集忘记初始化fa数组必须初始化为fa[i] i如果不初始化所有人的老大都是默认值 0find函数会直接错乱。贪心策略写反排序时重载小于号千万别写成从小到大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.cb.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 faufind(u); int favfind(v); //认v的老大为u的老大的老大 if(fau!fav) fa[fau]fav; } int main(){ ios::sync_with_stdio(false); cin.tie(0); cinnm; //初始化敌对关系为空 -1代表暂时还没有敌人 memset(enemy,-1,sizeof(enemy)); //初始化自己的老大是自己 for(int i1;in;i) fa[i]i; //把m对罪犯关系都存进去 for(int i1;im;i) cinno[i].ano[i].bno[i].c; //对no数组从大到小排序 怨气值高的优先处理 sort(no1,nom1); //遍历所有罪犯关系 for(int i1;im;i){ int uno[i].a; int vno[i].b; //如果u v两名罪犯的老大是同一个人 说明他们已经在同一个集合里 //则代表为了最大化满足前面那些更大怨气值的罪犯能不在一个监狱 //u v现在不得不处于同一个监狱了 if(find(u)find(v)){ //当前的怨气值就是无法避免的最大冲突 coutno[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 cout0; return 0; }